گرامر درخت مجاورت (TAG) یک قاعده ی گرامری است که توسط آراویند جوشی(Aravind Joshi) تعریف شده است. گرامرهای درخت مجاورت تاحدی شبیه گرامرهای مستقل از متن هستند اما واحد مقدماتی بازنویسی در اینجا به جای نماد، درخت است.اگرچه گرامرهای مستقل از متن قواعدی برای بازنویسی نمادها به عنوان رشته ای از سایر نمادها دارند، گرامرهای درخت مجاورت نیز قواعدی برای بازنویسی نودهای درخت ها به عنوان سایر درخت ها دارند. (بخش درخت (نظریه گراف) و درخت (ساختار داده) را ببینید.)
درخت (نظریه گراف)
درخت (ساختار داده)
TAG از مطالعات جوشی و دانشجویانش بر روی خانواده گرامرهای مجاورت (AG) و "گرامر رشته ای" توسط زلیگ هاریس به دست آمد. گرامرهای مجاورت ویژگی های درونی مرکزی (Endocentric) یک زبان را به شیوه ای طبیعی و مؤثر کنترل می کنند اما توصیف خوبی از ساختارهای بیرونی مرکزی (Exocentric) ندارد. صبحت اصلی بازنویسی گرامر یا دستور زبان ساختار عبارت (PSG) است.
در سال 1969، جوشی یک خانواده از دستور زبان معرفی کرد که مورد استفاده ی این مکمل، با ترکیب این دو نوع از قوانین قرار می گیرد. چند قانون بازنویسی بسیار ساده برای تولید واژگان رشته ها که برای بررسی قوانین مورد استفاده قرار می گیرد، کافی است. این خانواده از سلسله مراتب چامسکی-شواتزنبرگ(Chomsky-Schützenberger) متمایز است اما به صورتی جالب و زبانی اتصال دارد. رشته های مرکزی و رشته های کمکی همچنین می تواند توسط گرامر وابستگی و با اجتناب از محدودیت های سیستم بازنویسی به طور کامل تولید شوند.
قوانین در TAG ، درختانی با یک گره برگ خاص به نام گره پایانی (انتهایی) می باشند که به یک کلمه وصل شده است. درختان اصلی در TAG دو نوع دارند:درختان اولیه (که اغلب با ' α {\displaystyle \alpha } ' نشان داده می شود)درختان کمکی (' β {\displaystyle \beta } ')درختان اولیه نشان دهنده ی روابط بنیادی است، در حالی که درختات کمکی اجازه بازگشت را می دهد.گره ریشه و گره پایانی درختان کمکی با علامتی یکسان، نشاندار شده اند.اشتقاق با یک درخت اولیه شروع می شود، ترکیب از طریق تعویض یا الحاق انجام می شود.تعویض؛ گره مرزی را با درخت دیگری که گره بالای آن دارای همان برچسب می باشد، جایگزین می کند.برچسب گره ریشه / پایانی درخت کمکی باید مطابق با برچسب گره ای باشد که به آن متصل شده است.الحاق در نتیجه می تواند تأثیری به شکل تلاقی یک درخت کمکی به مرکز یک درخت دیگر داشته باشد. سایر مدل های TAG اجازه ی درختان جز، درختان با گره های متعدد پایانی و دیگر تعمیم ها را می دهد.
درخت (نظریه گراف)
درخت (ساختار داده)
TAG از مطالعات جوشی و دانشجویانش بر روی خانواده گرامرهای مجاورت (AG) و "گرامر رشته ای" توسط زلیگ هاریس به دست آمد. گرامرهای مجاورت ویژگی های درونی مرکزی (Endocentric) یک زبان را به شیوه ای طبیعی و مؤثر کنترل می کنند اما توصیف خوبی از ساختارهای بیرونی مرکزی (Exocentric) ندارد. صبحت اصلی بازنویسی گرامر یا دستور زبان ساختار عبارت (PSG) است.
در سال 1969، جوشی یک خانواده از دستور زبان معرفی کرد که مورد استفاده ی این مکمل، با ترکیب این دو نوع از قوانین قرار می گیرد. چند قانون بازنویسی بسیار ساده برای تولید واژگان رشته ها که برای بررسی قوانین مورد استفاده قرار می گیرد، کافی است. این خانواده از سلسله مراتب چامسکی-شواتزنبرگ(Chomsky-Schützenberger) متمایز است اما به صورتی جالب و زبانی اتصال دارد. رشته های مرکزی و رشته های کمکی همچنین می تواند توسط گرامر وابستگی و با اجتناب از محدودیت های سیستم بازنویسی به طور کامل تولید شوند.
قوانین در TAG ، درختانی با یک گره برگ خاص به نام گره پایانی (انتهایی) می باشند که به یک کلمه وصل شده است. درختان اصلی در TAG دو نوع دارند:درختان اولیه (که اغلب با ' α {\displaystyle \alpha } ' نشان داده می شود)درختان کمکی (' β {\displaystyle \beta } ')درختان اولیه نشان دهنده ی روابط بنیادی است، در حالی که درختات کمکی اجازه بازگشت را می دهد.گره ریشه و گره پایانی درختان کمکی با علامتی یکسان، نشاندار شده اند.اشتقاق با یک درخت اولیه شروع می شود، ترکیب از طریق تعویض یا الحاق انجام می شود.تعویض؛ گره مرزی را با درخت دیگری که گره بالای آن دارای همان برچسب می باشد، جایگزین می کند.برچسب گره ریشه / پایانی درخت کمکی باید مطابق با برچسب گره ای باشد که به آن متصل شده است.الحاق در نتیجه می تواند تأثیری به شکل تلاقی یک درخت کمکی به مرکز یک درخت دیگر داشته باشد. سایر مدل های TAG اجازه ی درختان جز، درختان با گره های متعدد پایانی و دیگر تعمیم ها را می دهد.
wiki: گرامر درخت مجاورت