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

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

پیش زمینه

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

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

سیستم‌های بازنویسی بدون متن خطی/ گرامرهای مستقل از متن متعدد از سلسله مراتب دو بعدی قدرت زایشی با توجه به دو پارامتر خاص گرامر تحت عنوان 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توصیف شود.