گرامرهای نوع یک یا حساس به متن

در این ویدئوی آموزشی به بررسی ماشین های نوع یک یا حساس به متن خواهیم پرداخت.

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

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

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

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

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

آلفا ‌می‌دهد بتا، بصورتیکه آلفا و بتا شامل ترکیبی از ترمینال‌ها و متغیرها هستند.

گرامرهای حساس به متن خاصیت انبساطی دارند یعنی طول شبه جمله سمت راست بیشتر از طول شبه جمله سمت چپ است.

زبان‌هایی که توسط گرامرهای حساس به متن پذیرفته شده زبان‌های حساس به متن گفته می‌شوند.

قانون S → λ فقط در صورتی که در طرف دوم هیچ کدام از قوانین s ظاهر نشده باشد می تواند وجود داشته باشد.

ماشین کراندار خطی مانند ماشین تورینگ است که دارای حافظه نامحدود است ولی فقط قسمتی از آن را می تواند استفاده کند که تابعی از ورودی است.

برای تعیین این محدوده ازنماد ] برای انتهای محدوده و [ برای ابتدای محدوده استفاده می شود. این نمادها نمی توانند بازنویسی شوند.

این ماشین برای گرامر های حساس به متن استفاده می شود.

حال به چند خاصیت زبان های حساس به متن اشاره میکنیم.

• گرامرهای حساس به متن حتماً بازگشتی (تصمیم پذیر) هستند.
• ولی هر گرامر تصمیم پذیر حتماً حساس به متن نیست.
• زبان‌های حساس به متن نسبت به عمل متمم، بستار ستاره‌ای، معکوس و همریختی بسته هستند.
• دو گرامر حساس به متن ، نسبت به عمل‌های اجتماع، اشتراک و اتصال بسته هستند.

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

رشته هایی که توسط این زبان پذیرفته می شوند شامل دو رشته‌ی مشابه شامل a و b است که با حرف c از هم جدا شده اند.

کوچکترین رشته ای که توسط این زبان پذیرفته می شود رشته c است،  پس اولین متغیری که تعریف می شود باید حرف C را به تنهایی تولید کند.

با توجه به اینکه  زیر رشته‌هایی که در دو طرف C قرار دارند یکسان هستند ، باید به ازای هر حرف a در سمت چپ یک حرف a در سمت راست در همان موقعیت داشته باشیم هم چنین برای حرف b.

با استفاده از متغیرهای qa و qb نشان میدهیم که کدام حرف اکنون تولید شده است مثلاً qa نشان دهنده تولید حرف a است .

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

در w سمت چپ هر زمانی نیاز باشد که حرفی اضافه شود به قبل حرف c اضافه می شود و در w سمت راست باید قبل از ¨ یا جایگزین آن حرفی قرار بگیرد.

بنابراین دو قانون جدید به مجموعه قوانین اضافه می شود که هر کدام مربوط به تولید یک حرف هست البته با توجه به نام متغیر ، مثلاً  qa حرف a را تولید می کند .

برای ادامه تولید، در رشته متغیر جدید q’ باید تعریف شود.

متغیر q’ در سمت راست حرف c تولید می شود ، هر گاه بصورت cq’ بود یعنی بدون هیچ فاصله ای از C بود، می‌تواند قبل از حرف C یک حرف جدید اضافه کند. مثلاً حرف a که با قانون aCq_a  قبل ازc تولید می شود و متغیر qa را به همراه خود دارد که نشان دهنده تولید حرف a هست.

قانون‌های که در این مرحله اضافه می شوند برای حرکت متغیرها به سمت راست یا چپ هستند .

مثلاً q_aa یعنی اگر qa قبل از a بود می تواند بصورت aqa شود یعنی تغییر مکان داده و به سمت راست a حرکت کند.

در این زبان حرف C به عنوان مرز  جدا کننده دو رشته محسوب می شود .

در زبان ww که هیچ مرزی وجود ندارد متغیرهایی را به عنوان مرز در نظر گرفته و در آخر جایگزین می کنیم .

مثلاً متغیر E و F در مرحله آخر با a جایگزین شود و متغیر Gو H با حرف b جایگزین شود.