گرامر درخت مجاورت: تفاوت میان نسخه‌ها

{{حذف سریع|[[وپ:محس#م۷|سرشناسی فرد یا موضوع مقاله را نشان نمی‌دهد]]}}

 

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

اگرچه گرامرهای مستقل از متن قواعدی برای بازنویسی نمادها به عنوان رشته ای از سایر نمادها دارند، گرامرهای درخت مجاورت نیز قواعدی برای بازنویسی نودهای درخت ها به عنوان سایر درخت ها دارند. (بخش [[درخت (نظریه گراف)]] و [[درخت (ساختار داده)]] را ببینید.)

 

 

TAG از مطالعات جوشی و دانشجویانش بر روی خانواده گرامرهای مجاورت (AG)<ref name="JoshiKosarajuYamada1969">{{cite paper

| title = String Adjunct Grammars

| year = 1969

{{Citation

| last =Joshi

| mr =

| zbl =

{{Citation

| last =Joshi

| mr =

| zbl =

</ref> و "گرامر رشته ای" توسط [[زلیگ هاریس]] به دست آمد.<ref>{{cite book

| last =Harris

| mr =

| zbl =

 

در سال 1969، جوشی یک خانواده از دستور زبان معرفی کرد که مورد استفاده ی این مکمل، با ترکیب این دو نوع از قوانین قرار می گیرد. چند قانون بازنویسی بسیار ساده برای تولید واژگان رشته ها که برای بررسی قوانین مورد استفاده قرار می گیرد، کافی است. این خانواده از [[سلسله مراتب چامسکی-شواتزنبرگ]](Chomsky-Schützenberger) متمایز است اما به صورتی جالب و زبانی اتصال دارد.<ref name="Joshi1969">{{cite paper

| title = Properties of Formal Grammars with Mixed Types of Rules and Their Linguistic Relevance

| year = 1969

| last = Joshi

| first = Aravind

| year = 2003

| booktitle = Proceedings of the Conference on Meaning-Text Theory

| title = A Lexicalized Tree Adjoining Grammar for English

| url = http://www.cis.upenn.edu/~xtag/tech-report/}}</ref>

 

قوانین در TAG ، درختانی با یک گره برگ خاص به نام گره پایانی (انتهایی) می باشند که به یک کلمه وصل شده است. درختان اصلی در TAG دو نوع دارند:

درختان اولیه (که اغلب با '<math>\alpha</math>' نشان داده میشود)

| pages = 354

| publisher = Prentice Hall

گره ریشه و گره پایانی درختان کمکی با علامتی یکسان، نشاندار شده اند.

[[اشتقاق]] با یک درخت اولیه شروع می شود، ترکیب از طریق تعویض و یا الحاق انجام میشود.

الحاق در نتیجه می تواند تاثیری به شکل تلاقی یک درخت کمکی به مرکز یک درخت دیگر داشته باشد. <ref name="joshi-rambow2003"/> سایر مدل های TAG اجازه ی درختان جز، درختان با گره های متعدد پایانی و دیگر تعمیم ها را می دهد.

 

گرامر درخت مجاورت می تواند (از لحاظ توانایی ضعیف تولیدی ) بسیار از [[گرامر مستقل از متن]] قوی تر باشد، اما نسبت به [[سیستم بازنویسی مستقل از متن خطی]]<ref>Kallmeyer, Laura (2010). Parsing Beyond Context-Free Grammars. Springer. Here: p.215-216</ref>، [[ایندکس]]<ref group=note>since for each tree-adjoining grammar, a linear indexed grammar can be found producing the same language, see [[#Equivalences|below]], and for the latter, a weakly equivalent (proper) indexed grammar can be found, in turn, see [[Indexed grammar#Computational Power]]</ref> یا [[گرامر حساس به متن]] کمتر قدرتمند هست.

TAG می تواند زبان مربعات (که در ان برخی از رشته های دلخواه تکرار شده است) و زبان <math>\{a^n b^n c^n d^n | 1 \le n \}</math> را توصیف کند.

| title = Natural Language Processing: Theoretical, Computational, and Psychological Perspectives

| editor = D. Dowty, L. Karttunen, and A. Zwicky, (eds.)

 

 

ویجی-شنکر و ویر (1994) <ref name="vijayshankarAndWeir1995">Vijay-Shanker, K. and Weir, David J. 1994. ''The Equivalence of Four Extensions of Context-Free Grammars''. Mathematical Systems Theory 27(6): 511–546.</ref> نشان داده اند که [[گرامر های ایندکس خطی]]، [[گرامر های دسته ترکیبی]]، گرامر های درخت مجاورت و گرامر هد ([[Head Grammars]]) هم ارزی معادل ضعیفی دارند.

 

گرامر درخت مجاورت لغوی (LTAG) یک نوع از ATG است که در آن هر درخت ابتدایی(اولیه یا کمکی) با لغت همراه است.

گرامر لغوی برای زبن انگلیسی توسط گروه پژوهشی XTAG موسسه پژوهش در علوم شناختی در دانشگاه پنسیلوانیا توسعه داده شده است.<ref name="xtagenglish"/>

 

*[[درخت (نظریه گراف)]]

*[[درخت (ساختار داده)]]

 

 

*[http://www.cis.upenn.edu/~xtag/ The XTAG project], which uses a TAG for natural language processing.

*[http://www.let.rug.nl/~vannoord/papers/diss/diss/node59.html A tutorial on TAG]

*[http://mgkit.gforge.inria.fr/ The Metagrammar Toolkit] which provides several tools to edit and compile [[MetaGrammars]] into TAGs. It also include a wide coverage French Metagrammars.

*[http://www.loria.fr/~azim/LLP2/help/fr/index.html LLP2] A [[lexicalized tree adjoining grammar]] parser which provides an easy to use graphical environment (page in French)