نمونه سوالات مبانی نظریه محاسبه (استخدامی)

دانلود رایگان نمونه سوالات مبانی نظریه محاسبه با جواب (استخدامی)

برای دانلود رایگان اینجا کلیک کنید

قسمتی از سوالات مبانی نظریه محاسبه :

۱- کدام گزینه در مورد الگوریتم CYK درست است؟

الف. الگوریتم CYK عضویت با عدم عضویت رشته ها در زبان های تولید شده در فرم نرمال چامسکی را با استفاده از یک رویکرد بالا به پایین تر بررسی می کند

ب. الگوریتم CYK عضویت با عدم عضویت رشته ها در زبان های تولید شده در فرم نرمال گریباخ را با استفاده از یک رویکرد بالا به پایین تر بررسی می کند

ج. الگوریتم CYK عضویت با عدم عضویت رشته ها در زبان های تولید شده در فرم نرمال چامسکی را با استفاده از یک رویکرد پایین به بالا تر بررسی می کند ☑

د. الگوریتم CYK عضویت با عدم عضویت رشته ها در زبان های تولید شده در فرم نرمال گریباخ را با استفاده از یک رویکرد بالا به پایین تر بررسی می کند

۲- خانواده زبان های مستقل از متن تحت کدامیک از اعمال زیر بسته نیست؟

الف. بستار ستاره ای

ب. الحاق

ج. مکمل گیری ☑

د. همربختی

۳- کدام نوع آتوماتا مشابه یک آتوماتای متناهی با یک حافظه نا محدود است و به عنوان یک مدل دقیق از یک کامپیوتر همه منظوره در نظر گرفته می شود؟

الف. اتومای پشته ای نامعین

ب. اتومانای پشته ای معین

ج. اتومانای کرندارد خطی

د. ماشین نورپنگ ☑

۴- با توجه به سه مفهوم زبان گرامر و اتوماتا کدامیک از گزینه های زیر صحیح نیست؟

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

ب. محدودیت های اعمال شده رو قوانین گرامر با افزایش شماره گرامر کاهش می یابد بنابراین گرامر نوع صفر محدودترین نوع گرامر محسوب می شود ☑

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

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

۵- کدامیک از جملات زیر در ارتباط با مفهوم اشتقاق و ابهام درگرامارهای مستقل از متن صحیح نیست؟

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

ب. درخت اشقاق تریتب استفاده از قوانین را مشخص نمی کند و تنها نشان می دهد که علائم نهایی رشته متعلق به کدام غیر پایانه گرامر می باشند

ج. یک گرامرمستقل از متن مبهم است اگر برای یک رشته w یک اشتقاق راست داشته باشد ☑

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

۶- کدام یک از گزینه های زیر در رابطه با گرامرهای منظم صحیح است؟

الف. هر گرامر خطی یک گرامر منظم است

ب. هر گرامر خطی خطی راست است

ج. یک گرامر خطی راست یم گرامر منظم است ☑

د. سمت راست گرامرهای منظم وجود هر تعداد متغییر مجاز است

۷- خانواده زبان های مستقل از متن تحت عملیات اشتراک منظم بسته ………….و تحت عمل مکمل گیری بسته ……………

الف. است – است

ب. است – نیست ☑

ج. نیست – است

د. نیست – نیست

۸- کدام یک الز گزینه های زیر در ارتباط با زیان های مستقل از متن نادرست است؟

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

ب. برای گرامر مستقل از متن یک الگوریتم برای تصمیم گیری عضویت یا عدم عضویت رشته w در یک زبان L وجود دارد

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

د. خانواده زبان های مستقل از متن تحت اجتماعی اشتراک و الحاق بسته است ☑

۹- زبان های حساس به متن توسط کدام گروه از آتوماتو پذیرفته می شوند؟

الف. آتوماتای متناهی

ب. آتوماتای پشته ای

ج. آتوماتای کراندار خطی ☑

د. ماشین تورینگ

۱۰- کدام گزینه در رابطه با زبان های بازگشتی و حساس به متن صحیح نیست؟

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

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

ج. هر زبان حساس به متن بازگشتی  است

د. زبان های شمارش پذیر بازگشتی زیر مجموعه زبان های بازگشتی هستند ☑

۱۱- کدامیک از گزینه های زیر در ارتباط با زبان های مستقل از متن نادرست است؟

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

ب. برای گرامر مستقل از متن یک الگوریتم برای تصمیم گیری عضویت یا عدم عضویت رشته w در یک زبان L وجود دارد

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

د. خانواده زبان های مستقل از متن تحت اجتماع اشتراک و الحاق بسته است ☑

۱۲- زبان های حساس به متن توسط کدام گروه از آتوماتا پذیرفته می شوند؟

الف. اتوماتای متناهی

ب. آتوماتای پشته ای

ج. آتوماتای کرندار خطی ☑

د. ماشین تورینگ

۱۳- کدام گزینه در رابطه با زبان های بازگشتی و حساس به متن صحیح نیست؟

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

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

ج. هر زبان حساس به متن بازگشتی است

د. زبان های شمارش پذیر بازگشتی زیر مجموعه زبان های بازگشتی هستند ☑

۱۴- کدام گزینه صحیح است؟

الف.  خانواده زبان های مستقل از متن تحت اجتماع الحاق وبستاربسته است

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

ج.  خانواده  زبان ها مستقل از متن تحت مکمل و تفریق بسته هستند ☑

د.  برای هر گرامر مستقل از متنی الگوریتمی وجود دارد که بتواند تعیین کند آیا L تهی است یا خیر

۱۵- کدام گزینه صحیح است؟

الف. ماشین تورینگ نامعین از ماشین تورینگ معین قوی تر است

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

ج. ماشین تورینگ چند نوار نامعین قوی ترین نوع ماشین تورینگ است

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

۱۶- کدام گزینه صحیح است؟

الف. اتوماتای محدود نامعین قوی تر از آتوماتای محدود معین است

ب. آتومانای پشته ای معین نامعین معادل نیستند ☑

ج. ماشین تورینگ معین و مامعین معادل نیستند

د. ماشین تورینگ معین و ماشین پشته ای معین معادل هستند

۱۷- زبان مستقل از متن L در چه صورتی خطی خوانده می شود؟

الف. در صورتی که برای تولید آن گرامر مستقل از متن خطی وجود داشته باشد ☑

ب. در صورتی که برای پذیرش آن ماشین پشته ای نامعین وجود داشته باشد

ج. در صورتی که برای پذیرش آن ماشین تورینگ نامعین وجود داشته باشد

د. در صورتی که برای پذیرش آن ماشین تورینگ وجود داشته باشد

۱۸- کدام گزینه صحیح است؟

الف. طول رشته می تواند نامتناهی باشد

ب. تعداد اعضای الفبا می تواند نامتناهی باشد

ج. تعداد اعضای زبان می تواند نامنتناهی باشد

د. هر سه موارد  ☑

۱۹- کدام گزینه در مورد زبان های منظم صحیح است؟

الف. همه زبان های منظم منتاهی هستند

ب. همه زبان های متناهی منظم هستند ☑

ج. فقط برخی از زبان های متناهی منظم هستند

د. بر خی از زبان های متناهی منظم نیستند

۲۰- کدام گزینه صحیح است؟

الف. همه زبان های قابل پذیرش توسط ماشین های پشته ای متناهی هستند

ب. زبان هر گرامر به صورت خطی چپ توسط ماشین پشته ای قابل پذیرش است ☑

ج. هز زبان قابل پذیرش توسط ماشین پشته ای توسط NFA نیز قابل پذیرش است

د. تنها زبان‌های وابسته به متن توسط ماشین‌های پشته ای قابل پذیرش هستند

۲۱- کدام گزینه صحیح است؟

الف. پذیرنده های متناهی قطعی و غیر قطعی نیستند

ب. پذیرنده های متناهی غیر قطعی هم ارز اتوماتای پشته ای قطعی است

ج. پذیرنده های متناهی قطعی هم ارزر اتومانای پشته ای قطعی است

د. اتوماتاهای پشته ای قطعی و غیر قطعی هم ارز نیستند ☑

۲۲- کدام گزینه صحیح نمی باشد؟

الف. خانواده زبان مستقل از متن تحت عملگرهای اجتماع الحاق و بستار بسته هستند

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

ج. خانواده زبان های منظم تحت عملگر تقسیم بسته هستند

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

۲۳- در خصوص خانواده ماشین های تورینگ کدام گزینه صحیح است؟

الف. خانواده ماشین های تورینگ معین و نامعین هم ارز هستند

ب. خانواده ماشین های تورینگ تک نواره و چند نواره هم ارز هستند

ج. خانواده ماشین های تورینگ عمومی و چند بعدی هم ارز هستند

د. همه موارد ☑