فرمالیسم گرامر نیمه حساس به متن

در سال ۱۹۸۵، چندین محقق زبانشناسی توصیفی و آماری، مدارکی را در مقابل نظریه ایی فراهم آوردند که ساختار نحوی زبان طبیعی می‌تواند به‌طور کارآمد با گرامر مستقل از متن توصیف شود. در همان زمان، مرحله‌ای که به سطح بعدی وراثت چامسکی برای گرامر حساس به متن می‌رفت، غیرضروری و نامناسب تشخیص داده شد. در تلاش برای اشاره به قدرت رسمی دقیق مورد نیاز برای توصیف کافی نحو زبان طبیعی، آراویند جوشی، گرامرها (و زبان‌های مربوطه) را توصیف کرد که اندکی قدرتمندتر از گرامرهای مستقل از متن (زبان مستقل از متن) هستند. او این گرامرها را گرامرهای نیمه حساس به متن و زبان‌های مربوطه را زبان‌های نیمه حساس به متن نامید.

توصیفات جوشی از گرامرهای نیمه حساس به متن، تحت تأثیر کارهایش در گرامر درخت مجاورت (TAG) (tree-adjoining grammar) بود؛ بنابراین، جوشی همراه با دانشجویانش، ویجای شانکر و دیوید ویر، کشف کرد که TAG در مورد زبانه‌ای رشته‌ای کلی با گرامر رأس (HG)(head grammar) مستقلاً معرفی شده، برابر است. این با دو نتیجهٔ معادل مشابه گرامر شاخص گذاری خطی (LIG) و گرامر گروه‌بندی ترکیب‌کننده (CCG) دنبال شد که نشان داد ماهیت گرامر نیمه حساس به متن خیلی کلی بوده و مرتبط با فرمالیسم خاص نیست.

فرمالیسم معادل TAG، به‌طور کلی با معرفی سیستم‌های بازنویسی مستقل از متن خطی (LCFRS) ایجاد شده‌است. این گرامرها، سلسله مراتب نامحدودی برای زبان‌های رشته‌ای بین زبان‌های مستقل از متن و زبان‌های حساس به متن تعریف می‌کنند، همراه با زبان‌هایی که با فرمالیسم معادل TAG در انتهای پایینی سلسله مراتب ایجاد شده‌اند. به‌طور مستقل و هم‌زمان با LCFRS، هیرویوکی سرکی، فرمالیسم ضرورتاً مشابه گرامر مستقل از متن متعدد (چندگانه) (MCFG) را پیشنهاد کرد. LCFRS/MCFG گاهی اوقات تحت عنوان فرمالیسم کلی مشخص کردن گرامرهای نیمه حساس به متن مورد توجه است؛ بنابراین، چندین نویسنده بیان کردند بعضی ویژگی‌های توصیفی فرمالیسم معادل TAG با LCFRS/MCFG، حفظ نشده و زبان‌هایی وجود دارند که ویژگی‌های توصیفی گرامر نیمه حساس به متن را دربرداشته، اما با LCFRS/MCFG بوجود نیامده‌اند

سالیان اخیر منافع فزاینده‌ای را در کلاس محدود سیستم‌های بازنویسی بدون متن خطی Well-nested/ گرامرهای مستقل از متن متعدد مشاهده کرده‌است که کلاسی از گرامرهایی را تعریف می‌کند که به‌طور درستی فرمالیسم معادل TAG و سلسله مراتب نامحدود LCFRS/MCFG را شامل می‌شود.

علی‌رغم میزان قابل ملاحظهٔ کار روی موضوع، هیچ تعریف رسمی به‌طور کلی پذیرفته شده‌ای برای گرامر نیمه حساس به متن وجود ندارد.

بر طبق ویژگی اصلی جوشی، یک کلاس گرامرهای نیمه حساس به متن باید شامل ویژگی‌های زیر شود:

1. وابستگی سری تقاطعی محدود
   
2. توسعه ثابت
   
3. تجزیه و تحلیل پلی نامینال

علاوه بر این، پی برده‌اند که هر کلاس گرامرهای نیمه حساس به متن، باید بتواند زبان بدون متن را ایجاد کند.

توصیفات جوشی، تعریف رسمی نیستند. او بیان می‌کند:

"فقط یک توصیف اصلی وجود دارد زیرا شرایط ۱ و۳ وابسته به گرامر هستند، در حالیکه شرط ۲ وابسته به زبان بوده و شرایط ۱ باید به‌طور دقیق تری نسبت به آن چیزی که تاکنون انجام گرفته، مشخص شود." نویسندگان دیگر، ویژگی‌های جایگزین گرامر نیمه حساس به متن را بیان کردند که شکل تعاریف رسمی دارد. برای مثال، لورا کالمیر، چشم‌اندازی را بیان می‌کند که گرامر نیمه حساس به متن باید بیشتر به عنوان ویژگی کلاس‌های زبان تعریف شود تا ویژگی جوشی، یعنی کلاس گرامر. چنین تعاریف زبان مبنایی منجر به ماهیت مختلف مفاهیم نسبت به تعاریف جوشی می‌شوند.

وابستگی سری تقاطعی

عنوان وابستگی سری تقاطعی، به الگوهای نظم کلمه با ویژگی خاص به خصوص الگوهای verb-argument اشاره دارد که در جملهٔ تبعی در هلند و سوئیس و آلمان مشاهده شدند. الگوهای زیادی وجود دارند که می‌توانند استفاده شوند تا در مورد مستقل از متن بودن زبان طبیعی بحث شود؛ بنابراین نیازمند گرامرهای نیمه حساس به متن هستند تا وابستگی سری کلی را مدل کنند بدین معنی که این گرامرها باید قدرتمند تر از گرامرهای مستقل از متن باشند.

کالمیر، توانایی مدل یابی وابستگی سری تقاطعی را با توانایی ایجاد زبان کپی شناسایی می‌کند تا کلی گرایی اش را در دو کپی یا بیشتر ازwبسته به بعضی محدودیت‌ها شناسایی کند. این زبان‌ها مستقل از متن نیستند که می‌تواند با استفاده از لم تزریق برای زبان‌های مستقل از متن اثبات شود.

توسعهٔ ثابت زبان

اگر هر رشته‌ای در زبان رسمی، طولانی‌تر از رشتهٔ کوتاهتر بعدی در میزان ثابت (خاص زبان) باشد، زبان رسمی در حال توسعهٔ ثابت است. اگرچه بعضی نویسندگان بحث کردند که پدیدهٔ خاص در زبان طبیعی، توسعه و رشدی را نشان می‌دهد که نمی‌تواند بامیزان ثابت خاص زبان محدود شود، زبان‌هایی که این ویژگی را نقض می‌کنند اغلب ماورای ظرفیت انسان مورد توجه هستند.

فرمالیسم‌های گرامر نیمه حساس به متن (به خصوص LCFRS/MCFG)، ویژگی قوی تری را از توسعه ثابت تأمین می‌کنند که نیمه خطی بودن semilinearity نامیده می‌شود. زبان در صورتی نیمه خطی است که تصویرش تحت Parikh-mapping (توصیفی که موقعیت نسبی نمادها را در زنجیرهٔ زبان فراموش می‌کند، به‌طور مؤثری به عنوان گروه کلمات عمل می‌کند)، یک زبان منظم باشند. زبان نیمه خطی دارای توسعه ثابت است، اما هر زبانی با توسعه ثابت، نیمه خطی نیست.

تجزیه و تحلیل پلی نامینال

فرمالیسم گرامر، زمانی تحت عنوان تجزیه و تحلیل پلی نامینال نامیده می‌شود که مشکل عضویتش می‌تواند در کلاس پی حل شود. مسئله‌ای برای تصمیم‌گیری وجود دارد که مشروط بر گرامر G نوشته شده در فرمالیسم و رشتهٔ W، آیا W با G ایجاده شده یا آیا W بر طبق G گرامری است یا نه. پیچیدگی زمانی این مشکل بر حسب اندازهٔ ترکیبی G و W ترکیب شده‌است.

تحت چشم‌انداز گرامر نیمه حساس به متن به عنوان ویژگی کلاس‌های زبان، تجزیه و تحلیل پلی نامینال به مسئله عضویت زبان اشاره دارد. مسئله‌ای برای تصمیم‌گیری وجود دارد که برای زبان ثابت L، آیا رشتهٔ مشخص W متعلق به L است یا نه. پیچیدگی زمانی این مسئله بر حسب طول W ارزیابی شده و این سؤال را نادیده می‌گیرد که W چگونه مشخص شده‌است.

توجه کنید درک تجزیه و تحلیل پلی نامینال، ایده‌آل گرایی در حسی است که برای کاربردهای عملی نه تنها به سؤال بله/ خیر علاقه دارند که آیا جمله گرامری است یا نه، بلکه در ساختار نحوی، گرامر برای جمله تعیین می‌شود.

طی سالیان، تعداد زیاد فرمالیسم‌های گرامری معرفی شده که بعضی یا همهٔ ویژگی‌های توصیفی توسط جوشی را دربردارند. چندین مورد ویژگی‌هایی براساس سیستم جایگزین دارند که در این مقاله بحث نشده‌است. برای مثال، زبان‌های ایجاد شده با tree-adjoining grammar (گرامر درخت مجاورت) می‌تواند باembedded pushdown automata توصیف شود.

فرمالیسم‌های معادل TAG

• گرامر درخت مجاورت (TAG)
• گرامر رأس (HG)
• گرامر نمایه سازی شده (LIG)
• گرامر گروه‌بندی ترکیب‌کننده (CCG)
• Well-nested LCFRS/MCFG of fan-out 2

فرمالیسم‌های معادل LCFRS/MCFG

• سیستم بازنویسی بدون متن خطی (LCFRS)
• گرامرهای بدون متن متعدد (MCFG)
• گرامرهای متصل به درخت چندجزئی (MCTAG)
• گرامرهای Minimalist(MG)
• گرامرهای ساده (خطی، non-erasing، غیرخطی)، گرامرهای اتصال محدوده مثبت (SRCG).

فرمالیسم‌های معادل well-nested LCFRS/MCFG

• گرامرهای بزرگ منتشر نشده
• گرامرهای مستقل از متن متعدد (CCFG)
• سیستم‌های بازنویسی مستقل از متن خطیwell-nested
• گرامرهای مستقل از متن متعدد well-nested

ارتباط بین فرمالیسم‌ها

سیستم‌های بازنویسی بدون متن خطی/ گرامرهای مستقل از متن متعدد از سلسله مراتب دو بعدی قدرت زایشی با توجه به دو پارامتر خاص گرامر تحت عنوان fan- out and rank نامیده می‌شوند. به‌طور دقیق تر، زبان ایجاد شده با LCFRS/MCFG در fan-out f≥۱ و rank r≥ ۳ به طرز درستی شامل کلاس زبان‌های ایجاد شده با LCFRS/MCFG و fan-out f و rank r+1، همچنین کلاسی از زبان‌های ایجاد شده با LCFRS/MCFG و fan-out f+1و rank r می‌شود. در حضور well-nested، این سلسله مراتب در سلسله مراتب یک بعدی با توجه به fan-out تجزیه می‌شود زیرا LCFRS/MCFG می‌تواند در LCFRS/MCFG با معادل با fan-out و محدوده ۲ یکسان، انتقال یابد. در سلسله مراتب LCFRS/MCFG، زبان مستقل از متن می‌تواند با گرامر و با fan-out1 توصیف شود و برای این fan-out، هیچ تفاوتی بین گرامرهای کلی و well-nested وجود ندارد. فرمالیسم معادل TAG می‌تواند به عنوان LCFRS/MCFGwell-nestedاز fan-out2توصیف شود.

• گرامر درخت مجاورت
• تعمیم گرامر مستقل از متن
• ماشین پشته‌ای جاسازی‌شده

• Riny Huybregts. The Weak Inadequacy of Context-Free Phrase Structure Grammars. In Ger de Haan, Mieke Trommelen, and Wim Zonneveld, editors, Van periferie naar kern, pages 81–99. Foris, Dordrecht, The Netherlands, 1984.
• Stuart M. Shieber. Evidence Against the Context-Freeness of Natural Language. Linguistics and Philosophy, 8(3):333–343, 1985.
• David J. Weir and Aravind K. Joshi. Combinatory Categorial Grammars: Generative Power and Relationship to Linear Context-Free Rewriting Systems. In Proceedings of the 26th Annual Meeting of the Association for Computational Linguistics (ACL), pages 278–285, Buffalo, USA, 1988.