گرامرهای مستقل از متن

در این ویدئوی آموزشی به بررسی خواص زبان های مستقل از متن می پردازیم.

کیفیت فیلم بصورت پیش فرض بر روی حالت low تنظیم شده است و شما می توانید با استفاده از تنظیمات موجود، این آموزش را با بالاترین کیفیت مشاهده نمایید.

شما می توانید با استفاده از گزینه “متن فیلم”، متن مربوط به حل سوال را مشاهده کنید.

//******************************************************************************************************************************************//

 پیشنهاد می شود به همراه مشاهده این آموزش مروری بر مباحث ماشین های پشته ای،فرم های نرمال و زبان های منظم داشته باشید.

از جمله خواص زبان‌های مستقل از متن میتوان به موارد روبرو اشاره کرد. برای هر زبان مستقل از متن یک PDA وجود دارد. با استفاده از فرم گریباخ می توان یک PDA طراحی کرد. همچنین اشتراک یک زبان منظم و یک زبان مستقل از متن، یک زبان مستقل از متن است.

همچنین اگر L_۱ یک زبان مستقل از متن باشد،

*^L مستقل از متن است.

L^R مستقل از متن است.

اما این نسبت به عمل متمم بسته نیست.

اگر L_۱ و L_۲ زبان های مستقل از متن باشند،

اجتماع آن دو حتماً مستقل از متن است.

اتصال آن دو مستقل از متن است.

و نسبت به عمل اشتراک بسته نیست.

حال می خواهیم برای زبان رو برو یک گرامر مستقل از متن بنویسیم.

رشته‌هایی از a، b و c بطوری که رشته بصورت xcx نباشد و x هم شامل جایگشت‌های مختلف از a و b است.

این زبان شامل تمام رشته ها به جز رشته هایی که به صورت xcx است، می شود.

گرامر این زبان را با توجه به ویژگی های گرامرهای مستقل از متن می توان به صورت اجتماع چند گرامر مستقل از متن نوشت. به گونه ای که: زبان منظم L1 شامل رشته های است که تعداد تکرار حرف c برابر یک نباشد یعنی فقط حرف c برای ماشین مهم می‌باشد و حروف a و b هیچ محدودیتی ندارند. پس رشته های ورودی می تواند شامل صفر و بیش از ۲ حرف c باشد.

به دیاگرام حالت آن توجه کنید. وضعیت اولیه ماشین می تواند یک وضعیت نهایی بوده و همچنین ماشین بعد از مشاهده دو عدد c می تواند به وضعیت نهایی دوم برود و در این بین هر تعدادی از a و b می تواند دیده شود.

زبان L2 شامل رشته هایی بصورت x1cx2 است، بطوری که طول رشته x1 که قبل از c می باشد کوچکتر از طول رشته x2 که بعد از c است، باشد. این زبان را با استفاده از PDA می توان طراحی کرد.

همانطور که در دیاگرام حالت آن مشاهده می کنید، ماشین در وضعیت اول به ازای هربار مشاهده a یا b یک حرف A به بالای پشته اضافه می کند تا اینکه ورودی رشته حرف c شود. در چنین شرایطی ماشین وارد حالت جدیدی می شود بطوری که به ازای هر حرف a یا b از رشته ورودی یک حرف A از پشته پاپ می کند تا اینکه پشته خالی شود.

در چنین شرایطی با دیدن حتی یک حرف اضافه تر از a یا b ماشین به حالت نهایی می رود چون طول رشته دوم بزرگتر از رشته اول می شود.

زبان L3 شامل رشته هایی بصورت x1cx2 است که طول رشته x1 بزرگتر از x2 می باشد. در این حالت داشتن طول بیش از یک برای x1 و وجود حرف c در رشته ورودی از اجزای مهم این گرامر می باشد.

در ماشین به ازای هر حرف a یا b قبل از اینکه حرف c مشاهده شود یک حرف A در پشته پوش می شود. بعد از دیدن حرف c در ورودی، ماشین وضعیت جدیدی پیدا می کند. به گونه ای که یا با دیدن حروف a یا b یک حرف A از پشته پاپ می شود یا اینکه اگر هیچ ورودی دیگری وجود نداشت به ازای اینکه پشته خالی نباشد می توان به وضعیت نهایی رفت، یعنی تعداد حرف بیشتری در رشته x1 مشاهده شده باشد.

زبان L4، مجموعه‌ای از رشته ها را فراهم می کند که طول زیر رشته ها در دو طرف c در شرایطی می توانند مساوی باشند، ولی از آنجا که بعد از x1 در سمت چپ رشته، یک حرف a و در سمت راست رشته بعد از x2 یک حرف b آمده، تضمین کننده این است که زیر رشته ها با هم برابر نیستند، چون طول x1 برابر با x2 است.

همانطور که در دیاگرام ملاحظه می شود به ازای a و bهای مشاهده شده در زیررشته x1 حرف A در پشته پوش می شود و هنگامی که وارد رشته x2 شد، به ازای هر ورودی یک حرف A از پشته پاپ می کند. با ورودی ay1c و by2 هیچ حرفی از پشته پاپ نمی شود.

زبان L5 شبیه به L4 است با این تفاوت که در رشته اول حرف b و در رشته دوم حرف a وجود دارد.

به دیاگرام حالت آن توجه کنید.

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

متمم زبان L، زبان wcw است ولی چون گرامرهای مستقل از متن نسبت به عمل متمم بسته نیستند، به طور حتم نمی توان گفت که متمم گرامر یعنی wcw هم یک گرامر مستقل از متن است.