حل تشریحی سوالات نظریه زبان‌ها و ماشین‌ها - کنکور ارشد مهندسی کامپیوتر 1401
منوی آزمون (درس ها)
سوالات نظریه زبان‌ها و ماشین‌ها
5 سوال51.
چه تعداد از گزاره های زیر درست است؟
- هر زبان تشخیص ناپذیر تورینگ، تصمیم ناپذیر است.
- مجموعه همه زبان‌های نامنظم روی یک الفا، یک مجموعه شمارای نامتناهی است.
- مجموعه همه ماشین‌های تورینگ روی یک الفبا، یک مجموعه شمارای نامتناهی است.
- هرزبان نامتناهی تشخیص پذیر تورینگ، یک زیر مجموعه نامتناهی تصمیم پذیر است.
1)
4
2)
3
3)
2
4)
1
52.
زبان پذیرفته شده توسط پذیرنده پشته‌ای PDA رو به رو، کدام گزینه است؟( تعداد حرف a در رشته w را مشخص میکند.)
1)
2)
3)
4)
53.
زبان در نظربگیرید.
برای تولید زبان بالا گرامر زیر پیشنهاد شده است. (S متغیر شروع و a تنها حرف الفبا است.)
کدام گزینه در خصوص نوع گرامر بالا و عبارتی که بایستی بجای ? قرار گیرد، درست است؟
1)
نوع صفر (بدون محدودیت)-R
2)
نوع یک (حساس به متن)-R}
3)
نوع صفر (بدون محدودیت)-H
4)
نوع یک(حساس به متن)-aH
54.
فرض کنید L1 و L2 زبان های مستقل از متن (context-free) و R زبانی منظم (regular) باشند. کدام گزینه، لزوما زبانی مستقل از متن نخواهد بود؟
1)
2)
3)
4)
55.
گرامر روبه رو کدام یک از زبان های زیر را توصیف میکند؟
1)
2)
3)
4)