دانلود رایگان سوالات نظریه اتوماتها و زبانها با جواب (استخدامی)
قسمتی از سوالات نظریه اتوماتها و زبانها :
– زبان های حساس به متن توسط کدام گروه از آتوماتو پذیرفته می شوند؟
الف. آتوماتای متناهی
ب. آتوماتای پشته ای
ج. آتوماتای کراندار خطی ☑
د. ماشین تورینگ
– کدام گزینه در رابطه با زبان های بازگشتی و حساس به متن صحیح نیست؟
الف. یک زبان بازگشتی است اگر یک الگوریتم عضویت برای آن وجود داشته باشد
ب. هر زبانی که توسط یک گرامر بدون محدودیت تولید می شود شمارش پذیر بازگشتی است
ج. هر زبان حساس به متن بازگشتی است
د. زبان های شمارش پذیر بازگشتی زیر مجموعه زبان های بازگشتی هستند ☑
– کدامیک از گزینه های زیر در ارتباط با زبان های مستقل از متن نادرست است؟
الف. خانواده زبان های مستقل از متن تحت اشتراک منظم بسته است
ب. برای گرامر مستقل از متن یک الگوریتم برای تصمیم گیری عضویت یا عدم عضویت رشته w در یک زبان L وجود دارد
ج. خانواده زبان های مستقل از متن تحت مکمل گیری بسته نیست
د. خانواده زبان های مستقل از متن تحت اجتماع اشتراک و الحاق بسته است ☑
– زبان های حساس به متن توسط کدام گروه از آتوماتا پذیرفته می شوند؟
الف. اتوماتای متناهی
ب. آتوماتای پشته ای
ج. آتوماتای کرندار خطی ☑
د. ماشین تورینگ
– کدام گزینه در رابطه با زبان های بازگشتی و حساس به متن صحیح نیست؟
الف. یک زبان بازگشتی است اگر یک الگوریتم عضویت برای آن وجود داشته باشد
ب. هر زبانی که توسط یک گرامر بدون محدودیت تولید می شود شمارش پذیر بازگشتی است
ج. هر زبان حساس به متن بازگشتی است
د. زبان های شمارش پذیر بازگشتی زیر مجموعه زبان های بازگشتی هستند ☑
– کدام گزینه صحیح است؟
الف. خانواده زبان های مستقل از متن تحت اجتماع الحاق وبستاربسته است
ب. خانواده زبان های مستقل از متن تحت اشتراک منظم بسته است منظور از اشتراک یک زبان منظم با یک زبان مستقل از متن است
ج. خانواده زبان ها مستقل از متن تحت مکمل و تفریق بسته هستند ☑
د. برای هر گرامر مستقل از متنی الگوریتمی وجود دارد که بتواند تعیین کند آیا L تهی است یا خیر
– کدام گزینه صحیح است؟
الف. ماشین تورینگ نامعین از ماشین تورینگ معین قوی تر است
ب. ماشین تورینگ چند نواره از ماشین تورینگ تک نواره قوی تر است
ج. ماشین تورینگ چند نوار نامعین قوی ترین نوع ماشین تورینگ است
د. ماشین تورینگ چند نواره با ماشین تورینگ تک نواره معین معادل هستند ☑
– کدام گزینه در مورد الگوریتم CYK درست است؟
الف. الگوریتم CYK عضویت با عدم عضویت رشته ها در زبان های تولید شده در فرم نرمال چامسکی را با استفاده از یک رویکرد بالا به پایین تر بررسی می کند
ب. الگوریتم CYK عضویت با عدم عضویت رشته ها در زبان های تولید شده در فرم نرمال گریباخ را با استفاده از یک رویکرد بالا به پایین تر بررسی می کند
ج. الگوریتم CYK عضویت با عدم عضویت رشته ها در زبان های تولید شده در فرم نرمال چامسکی را با استفاده از یک رویکرد پایین به بالا تر بررسی می کند ☑
د. الگوریتم CYK عضویت با عدم عضویت رشته ها در زبان های تولید شده در فرم نرمال گریباخ را با استفاده از یک رویکرد بالا به پایین تر بررسی می کند
– خانواده زبان های مستقل از متن تحت کدامیک از اعمال زیر بسته نیست؟
الف. بستار ستاره ای
ب. الحاق
ج. مکمل گیری ☑
د. همربختی
– کدام نوع آتوماتا مشابه یک آتوماتای متناهی با یک حافظه نا محدود است و به عنوان یک مدل دقیق از یک کامپیوتر همه منظوره در نظر گرفته می شود؟
الف. اتومای پشته ای نامعین
ب. اتومانای پشته ای معین
ج. اتومانای کرندارد خطی
د. ماشین نورپنگ ☑
– با توجه به سه مفهوم زبان گرامر و اتوماتا کدامیک از گزینه های زیر صحیح نیست؟
الف. آتوماتای کراندار خطی با حافظه ای از هر دو سمت محدود پذیرنده زبان های حساس به متن معرفی می شود
ب. محدودیت های اعمال شده رو قوانین گرامر با افزایش شماره گرامر کاهش می یابد بنابراین گرامر نوع صفر محدودترین نوع گرامر محسوب می شود ☑
ج. زبان های نوع سوم قطعا نوع نیز می باشند اما هر زبان نوع دوم الزاما نوع سوم نیست
د. گرامتر مستقل از متن ابزاری برای تولیدزبان های نوع دوم می باشند که این گروه از زبان ها توسط آتومانای پشته ای پذیرفته می شوند
– کدام گزینه صحیح است؟
الف. همه زبان های قابل پذیرش توسط ماشین هایپشته ای، متناهی هستند
ب. زبان هر گرامر به صورت خطب چپ، توسط ماشین پشته ای قابل پذیرش است ☑
ج. هر زبان قابل پذیرش توسط ماشین پشته ای، توسط NFA نیز قابل پذیرش است
د. تنها زبان های وابسته به متن توسط ماشین های پشته ای قابل پذیرش هستند
– کدام گزینه صحیح است؟
الف. یک زبان منظم، می تواند فقط توسط یک DFA پذیرفته شود
ب. یک زبان منظم می تواند فقط یک DFA یا NFA پذیرفته شود
ج. یک زبان منظم می تواند فقط توسط یک DFA یا NFA یا PAD پذیرفته شود
د. یک زبان منظم می تواند فقط توسط یک DFA یا NFA یا PAD یا ماشین تورینگ پذیرفته شود ☑
– کدام یک از گزارهای زیر صحیح است؟
گزاره اول: ماشین کراندار خطی (LBA) قوی تر از ماشین پشته ای (PDA) است
گزاره دوم: ماشین متناهی (DFA) از ماشین پشته ای (PDA) ضعیف تر است
گزاره سوم: ماشین کراندار خطی LBA) هم ارز با ماشین تورینگ (TM) است
الف. فقط گزارهای اول و دوم ☑
ب. فقط گزارهای دوم و سوم
ج. فقط گزارهای اول و سوم
د. گزارهای اول و دوم و سوم
– کدامیک از جملات زیر در ارتباط با مفهوم اشتقاق و ابهام درگرامارهای مستقل از متن صحیح نیست؟
الف. نتیجه حاصل از اشتقاق راست و چپ رشته یکسانی را در پی دارد تنها تفاوت آنها در ترتیب استفاده از قوانین از گرامر است
ب. درخت اشقاق تریتب استفاده از قوانین را مشخص نمی کند و تنها نشان می دهد که علائم نهایی رشته متعلق به کدام غیر پایانه گرامر می باشند
ج. یک گرامرمستقل از متن مبهم است اگر برای یک رشته w یک اشتقاق راست داشته باشد ☑
د. یک گرامر مستقل از متن ذاتا مبهم است اگر هر گرامر تولید کننده آن مبهم باشد
– کدام یک از گزینه های زیر در رابطه با گرامرهای منظم صحیح است؟
الف. هر گرامر خطی یک گرامر منظم است
ب. هر گرامر خطی خطی راست است
ج. یک گرامر خطی راست یم گرامر منظم است ☑
د. سمت راست گرامرهای منظم وجود هر تعداد متغییر مجاز است
– خانواده زبان های مستقل از متن تحت عملیات اشتراک منظم بسته ………….و تحت عمل مکمل گیری بسته ……………
الف. است – است
ب. است – نیست ☑
ج. نیست – است
د. نیست – نیست
– زبان مستقل از متن L در چه صورتی خطی خوانده می شود؟
الف. در صورتی که برای تولید آن گرامر مستقل از متن خطی وجود داشته باشد ☑
ب. در صورتی که برای پذیرش آن ماشین پشته ای نامعین وجود داشته باشد
ج. در صورتی که برای پذیرش آن ماشین تورینگ نامعین وجود داشته باشد
د. در صورتی که برای پذیرش آن ماشین تورینگ وجود داشته باشد
– کدام گزینه صحیح است؟
الف. طول رشته می تواند نامتناهی باشد
ب. تعداد اعضای الفبا می تواند نامتناهی باشد
ج. تعداد اعضای زبان می تواند نامنتناهی باشد
د. هر سه موارد ☑
– کدام یک از گزینه های زیر در ارتباط با زیان های مستقل از متن نادرست است؟
الف. خانواده زبان های مستقل از یک متن تحت اشتراک منظم بسته ایت
ب. برای گرامر مستقل از متن یک الگوریتم برای تصمیم گیری عضویت یا عدم عضویت رشته w در یک زبان L وجود دارد
ج. خانواده زبان های مستقل از متن تحت مکمل گیری بسته نیست
د. خانواده زبان های مستقل از متن تحت اجتماعی اشتراک و الحاق بسته است ☑
– کدام گزینه صحیح است؟
الف. اتوماتای محدود نامعین قوی تر از آتوماتای محدود معین است
ب. آتومانای پشته ای معین نامعین معادل نیستند ☑
ج. ماشین تورینگ معین و مامعین معادل نیستند
د. ماشین تورینگ معین و ماشین پشته ای معین معادل هستند
