در این ویدئوی آموزشی به بررسی ماشین های نوع صفر خواهیم پرداخت.
کیفیت فیلم بصورت پیش فرض بر روی حالت low تنظیم شده است و شما می توانید با استفاده از تنظیمات موجود، این آموزش را با بالاترین کیفیت مشاهده نمایید.
شما می توانید با استفاده از گزینه “متن فیلم”، متن مربوط به حل سوال را مشاهده کنید.
//******************************************************************************************************************************************//
پیشنهاد می شود قبل از مشاهده این آموزش، مروری بر مباحث گرامرهای نوع یک، دوم و سوم داشته باشید. شما در پایان این آموزش می توانید تسلط بسیار مناسبی از ماشین‌های نوع صفر به دست آورید.
گرامر های نوع صفر یا گرامرهای نامقید، گرامرهایی هستند که قوانین در دو سمت شامل ترکیبی از ترمینال ها و متغیرها است و هیچ گونه محدودیت و قید و شرطی ندارند.
این گرامر ها با ماشین تورینگ قابل معادل سازی هستند.
زبان هایی که توسط این گرامرها پیاده سازی می شوند، زبان های بازگشتی برشمردنی گفته می شوند.
اگر ماشین تورینگ M وجود داشته باشد که برای هر رشته عضو زبان، ماشین جواب yes بدهد در غیر این صورت جواب No بدهد. به خانواده این زبانها، بازگشتی یا Recursive گفته می شود.
اگر ماشین تورینگ M وجود داشته باشد که برای هر رشته عضو زبان، ماشین جواب yes بدهد و برای بقیه جوابی ندهد یا جواب No بدهد . به خانواده این زبانها، بازگشتی برشمردنی یا Recursive Enumerable گفته می شود.
در این دسته در مورد رشته‌هایی که جز زبان نیست، جوابی ندارد.
یک الگوریتم جهت شمارش عناصر یک زبان را روال برشمارش گویند. هر زبانی که دارای روال برشمارش باشد، یک زبان بازگشتی برشمردنی است.
اگر زبان L و متمم آن هر دو شمارش پذیر بازگشتی باشند، آنگاه هر دو زبان بازگشتی هستند. اگر L بازگشتی باشد، آنگاه متمم آن هم بازگشتی است و در نتیجه هر دو شمارش پذیر بازگشتی هستند.
حال به بررسی یک نمونه سوال می پردازیم. برای هر زبان L1 و L2 بطوری که L1 مستقل از متن و L2 یک زبان بازگشتی شمردنی ولی نه بازگشتی باشد. کدام یک از گزینه‌ها در موارد زیر الزاماً درست است؟
۱- L1’ ( متمم L1) بازگشتی است.
۲- L2’ ( متمم L2) بازگشتی است.
۳-L1’ ( متمم L1) مستقل از متن است.
۴-اجتماع L1’ و L2 بازگشتی برشمردنی است.
موارد را به ترتیب بررسی می کنیم:
مورد اول: متمم L1 بازگشتی است.
نکته‌های حائز اهمیت در تصمیم گیری این است که :
L1 یک گرامر مستقل از متن است.
گرامر مستقل از متن زیر مجموعه‌ای از گرامرهای بازگشتی هستند.
گرامرهای بازگشتی نسبت به عمل متمم بسته است.
بنابراین متمم L1 بازگشتی است و مورد اول درست است.
مورد دوم: متمم L2 بازگشتی است
زبان L2 یک زبان بازگشتی برشمردنی است.
گرامرهای بازگشتی برشمردنی نسبت به عمل متمم بسته نیستند.
بنابراین متمم L2 الزاماً بازگشتی نیست و مورد دوم یک عبارت همیشه درست نیست.
و اما مورد سوم: متمم L1 مستقل از متن است.
زبان L1 یک زبان مستقل از متن است.
گرامرهای مستقل از متن نسبت به عمل متمم بسته نیستند.
بنابراین متمم L1 الزاماً مستقل از متن نیست.
و مورد چهارم:
اجتماع L1’و L2 بازگشتی برشمردنی است.
L1’ بازگشتی و در نتیجه بازگشتی برشمردنی است.
گرامرهای بازگشتی برشمردنی نسبت به عمل اجتماع بسته است.
در نتیجه اجتماع L1’ و L2 بازگشتی برشمردنی می باشد.
در نتیجه گزینه D صحیح است یعنی موارد ۱ و ۴ درست هستند.