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

در زبان‌شناسی رایانشی، عنوان فرمالیسم‌های گرامر نیمه حساس به متن به چندین گرامر صوری اطلاق می‌شود که با هدف ارائه توصیفی نحو زبان توسعه یافته‌اند.
هر فرمالیسم گرامر نیمه حساس به متن، کلاسی از گرامر نیمه حساس به متن (گرامرهایی که می‌توانند در فرمالیسم مشخص شوند) و همچنین کلاس زبان نیمه حساس به متن (زبان‌های صوری ایجاد شده توسط گرامر) را تعریف می‌کند.
پیش زمینه
در سال ۱۹۸۵، چندین محقق زبانشناسی توصیفی و آماری، مدارکی را در مقابل نظریه ایی فراهم آوردند که ساختار نحوی زبان طبیعی می‌تواند به‌طور کارآمد با گرامر مستقل از متن توصیف شود. در همان زمان، مرحله‌ای که به سطح بعدی وراثت چامسکی برای گرامر حساس به متن می‌رفت، غیرضروری و نامناسب تشخیص داده شد. در تلاش برای اشاره به قدرت رسمی دقیق مورد نیاز برای توصیف کافی نحو زبان طبیعی، آراویند جوشی، گرامرها (و زبان‌های مربوطه) را توصیف کرد که اندکی قدرتمندتر از گرامرهای مستقل از متن (زبان مستقل از متن) هستند. او این گرامرها را گرامرهای نیمه حساس به متن و زبان‌های مربوطه را زبان‌های نیمه حساس به متن نامید.
توصیفات جوشی از گرامرهای نیمه حساس به متن، تحت تاثیر کارهایش در
گرامر درخت مجاورت (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 را شامل می‌شود.
ویژگی‌های توصیفی
علی رغم میزان قابل ملاحظه کار روی موضوع، هیچ تعریف رسمی به‌طور کلی پذیرفته شده‌ای برای گرامر نیمه حساس به متن وجود ندارد.
بر طبق ویژگی اصلی جوشی، یک کلاس گرامرهای نیمه حساس به متن باید شامل ویژگی‌های زیر شود:
۱) وابستگی سری تقاطعی محدود
۲) توسعه ثابت
۳) تجزیه و تحلیل پلی نامینال
علاوه بر این، پی برده‌اند که هر کلاس گرامرهای نیمه حساس به متن، باید بتواند
زبان بدون متن را ایجاد کند.
توصیفات جوشی، تعریف رسمی نیستند. او بیان می‌کند:
"فقط یک توصیف اصلی وجود دارد زیرا شرایط ۱ و۳ وابسته به گرامر هستند، در حالیکه شرط ۲ وابسته
به زبان بوده و شرایط ۱ باید به‌طور دقیق‌تری نسبت به آن چیزی که تاکنون انجام گرفته، مشخص شود."
نویسندگان دیگر، ویژگی‌های جایگزین گرامر نیمه حساس به متن را بیان کردند که شکل تعاریف رسمی دارد. برای مثال، لورا کالمیر، چشم‌اندازی را بیان می‌کند که گرامر نیمه حساس به متن باید بیشتر به عنوان ویژگی کلاس‌های زبان تعریف شود تا ویژگی جوشی، یعنی کلاس گرامر. چنین تعاریف زبان مبنایی منجر به ماهیت مختلف مفاهیم نسبت به تعاریف جوشی
می‌شوند.
وابستگی سری تقاطعی
عنوان وابستگی سری تقاطعی، به الگوهای نظم کلمه با ویژگی خاص به خصوص الگوهای 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توصیف شود.
گرامر درخت مجاورت
تعمیم گرامر مستقل از متن
ماشین پشته‌ای جاسازی‌شده