گرامر درخت مجاورت

گرامر درخت مجاورت (TAG) یک قاعده ی گرامری است که توسط آراویند جوشی(Aravind Joshi) تعریف شده‌است. گرامرهای درخت مجاورت تاحدی شبیه گرامرهای مستقل از متن هستند اما واحد مقدماتی بازنویسی در اینجا به جای نماد، درخت است. اگرچه گرامرهای مستقل از متن قواعدی برای بازنویسی نمادها به عنوان رشته‌ای از سایر نمادها دارند، گرامرهای درخت مجاورت نیز قواعدی برای بازنویسی نودهای درخت‌ها به عنوان سایر درخت‌ها دارند. (بخش درخت (نظریه گراف) و درخت (ساختار داده) را ببینید.)

تاریخچه

TAG از مطالعات جوشی و دانشجویانش بر روی خانواده گرامرهای مجاورت (AG)^[۱] و "گرامر رشته ای" توسط زلیگ هاریس به دست آمد.^[۲] گرامرهای مجاورت ویژگی‌های درونی مرکزی (Endocentric) یک زبان را به شیوه ای طبیعی و مؤثر کنترل می‌کنند اما توصیف خوبی از ساختارهای بیرونی مرکزی (Exocentric) ندارد. صبحت اصلی بازنویسی گرامر یا دستور زبان ساختار عبارت (PSG) است.

در سال 1969، جوشی یک خانواده از دستور زبان معرفی کرد که مورد استفاده ی این مکمل، با ترکیب این دو نوع از قوانین قرار می‌گیرد. چند قانون بازنویسی بسیار ساده برای تولید واژگان رشته‌ها که برای بررسی قوانین مورد استفاده قرار می‌گیرد، کافی است. این خانواده از سلسله مراتب چامسکی-شواتزنبرگ(Chomsky-Schützenberger) متمایز است اما به صورتی جالب و زبانی اتصال دارد.^[۳] رشته‌های مرکزی و رشته‌های کمکی همچنین می‌تواند توسط گرامر وابستگی و با اجتناب از محدودیت‌های سیستم بازنویسی به‌طور کامل تولید شوند.^[۴][۵]

شرح

قوانین در TAG ، درختانی با یک گره برگ خاص به نام گره پایانی (انتهایی) می‌باشند که به یک کلمه وصل شده‌است. درختان اصلی در TAG دو نوع دارند: درختان اولیه (که اغلب با '${\displaystyle \alpha }$' نشان داده می‌شود) درختان کمکی ('${\displaystyle \beta }$') درختان اولیه نشان دهنده ی روابط بنیادی است، در حالی که درختات کمکی اجازه بازگشت را می‌دهد.^[۶] گره ریشه و گره پایانی درختان کمکی با علامتی یکسان، نشاندار شده‌اند. اشتقاق با یک درخت اولیه شروع می‌شود، ترکیب از طریق تعویض یا الحاق انجام می‌شود. تعویض؛ گره مرزی را با درخت دیگری که گره بالای آن دارای همان برچسب می‌باشد، جایگزین می‌کند. برچسب گره ریشه / پایانی درخت کمکی باید مطابق با برچسب گره‌ای باشد که به آن متصل شده‌است. الحاق در نتیجه می‌تواند تأثیری به شکل تلاقی یک درخت کمکی به مرکز یک درخت دیگر داشته باشد.^[۴] سایر مدل‌های TAG اجازه ی درختان جز، درختان با گره‌های متعدد پایانی و دیگر تعمیم‌ها را می‌دهد.

پیچیدگی و کاربرد

گرامر درخت مجاورت می‌تواند (از لحاظ توانایی ضعیف تولیدی ) بسیار از گرامر مستقل از متن قوی تر باشد، اما نسبت به سیستم بازنویسی مستقل از متن خطی^[۷]، گرامر نمایه‌سازی شده یا گرامر حساس به متن کمتر قدرتمند هست. TAG می‌تواند زبان مربعات (که در ان برخی از رشته‌های دلخواه تکرار شده است) و زبان ${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|1\leq n\}}$ را توصیف کند. این نو ع از پردازش می‌تواند توسط یک ماشین پذیرنده ی پشته ای تعبیه شده، نمایش داده شود. زبان‌هایی با توان ۳(برای مثال رشته‌ای با ۳ بار تکرار) یا با بیش از چهار رشته کاراکتری متمایز با طول یکسان توسط دستور الحاق درختی قابل ایجاد نیست.

به این دلایل، گرامر درخت مجاورت اغلب به صورت زبان ملایم حساس به متن توصیف می‌شود.گمان می‌رود این کلاس‌های دستوری برای مدل کردن زبان‌های طبیعی کافی باشند، در حالی که همچنین در حالت عمومی تا حد مطلوبی قاعده مند می‌باشند.^[۸]

هم ارزی

ویجی-شنکر و ویر (1994) ^[۹] نشان داده اند که گرامرهای نمایه‌سازی شده خطی، گرامرهای دسته ترکیبی، گرامرهای درخت مجاورت و گرامر هد (Head Grammars) هم ارزی معادل ضعیفی دارند.

گرامر درخت مجاورت لغوی

گرامر درخت مجاورت لغوی (LTAG) یک نوع از ATG است که در آن هر درخت ابتدایی(اولیه یا کمکی) با لغت همراه است. گرامر لغوی برای زبن انگلیسی توسط گروه پژوهشی XTAG مؤسسه پژوهش در علوم شناختی در دانشگاه پنسیلوانیا توسعه داده شده‌است.^[۵]

جستارهای وابسته

• درخت (نظریه گراف)
• درخت (ساختار داده)

منابع

1. Joshi, Aravind; S. R. Kosaraju; H. Yamada (1969). "String Adjunct Grammars". Proceedings Tenth Annual Symposium on Automata Theory, Waterloo, Canada. Joshi, Aravind K.; Kosaraju, S. Rao; Yamada, H. M. (1972), "String Adjunct Grammars: I. Local and Distributed Adjunction", Information and Control, 21 (2): 93–116, doi:10.1016/S0019-9958(72)90051-4 Joshi, Aravind K.; Kosaraju, S. Rao; Yamada, H. M. (1972), "String Adjunct Grammars: II. Equational Representation, Null Symbols, and Linguistic Relevance", Information and Control, 21 (3): 235–260, doi:10.1016/S0019-9958(72)80005-6
2. Harris, Zellig S. (1962). String analysis of sentence structure. Papers on Formal Linguistics. Vol. 1. The Hague: Mouton & Co.
3. Joshi, Aravind (1969). "Properties of Formal Grammars with Mixed Types of Rules and Their Linguistic Relevance". Proceedings Third International Symposium on Computational Linguistics, Stockholm, Sweden.
4. Joshi, Aravind; Owen Rambow (2003). "A Formalism for Dependency Grammar Based on Tree Adjoining Grammar" (PDF). Proceedings of the Conference on Meaning-Text Theory.
5. "A Lexicalized Tree Adjoining Grammar for English".
6. Jurafsky, Daniel; James H. Martin (2000). Speech and Language Processing. Upper Saddle River, NJ: Prentice Hall. pp. 354.
7. Kallmeyer, Laura (2010). Parsing Beyond Context-Free Grammars. Springer. Here: p.215-216
8. Joshi, Aravind (1985). "How much context-sensitivity is necessary for characterizing structural descriptions". In D. Dowty, L. Karttunen, and A. Zwicky, (eds.) (ed.). Natural Language Processing: Theoretical, Computational, and Psychological Perspectives. New York, NY: Cambridge University Press. pp. 206–250. {{cite book}}: |editor= has generic name (help)
9. Vijay-Shanker, K. and Weir, David J. 1994. The Equivalence of Four Extensions of Context-Free Grammars. Mathematical Systems Theory 27(6): 511–546.

پیوند به بیرون

• The XTAG project, which uses a TAG for natural language processing.
• A tutorial on TAG
• Another tutorial with focus on comparison with Lexical Functional Grammar and grammars extraction from Treebank
• SemConst Documentation A quick survey on Syntax and Semantic Interface problematic within the TAG framework.
• The TuLiPa project بایگانی‌شده در ۲۲ ژوئیه ۲۰۱۲ توسط Wayback Machine The Tübingen Linguistic Parsing Architecture (TuLiPA) is a multi-formalism syntactic (and semantic) parsing environment, designed mainly for multi-component tree adjoining grammars with tree tuples
• The Metagrammar Toolkit بایگانی‌شده در ۳ مارس ۲۰۱۶ توسط Wayback Machine which provides several tools to edit and compile MetaGrammars into TAGs. It also include a wide coverage French Metagrammars.
• LLP2 A lexicalized tree adjoining grammar parser which provides an easy to use graphical environment (page in French)