دانلود رایگان نمونه سوالات نظریه محاسبه با جواب (استخدامی)
برای دانلود رایگان اینجا کلیک کنید
قسمتی از سوالات نظریه محاسبه :
– مجموعه ۱ را شما را گویند هر گاه………
الف. محدود باشد.
ب. محدود با هم اندازه با N باشد. ☑
ج. نامتناهی باشد.
د. بزرگتر از N باشد.
– یک زبان تصمیم پذیر است اگر و تنها اگر …………
الف. خود زبان و مکمل آن تشخیص پذیر باشد. ☑
ب. پرشمارنده ای برای برشمردن آن موجود باشد.
ج. ماشین تورینگ نامعینی برای تشخیص آن زبان موجود باشد.
د. یک ماشین تورینگ چند نواره برای تشخیص آن زبان موجود باشد.
– کدامیک از گرینه های زیر در مورد ماشین تورینگ صحیح است؟
الف. ماشین تورینگ دارای حافظه محدود می باشد.
ب. ماشین تورینگ مشابه اتوماتای مشاهی می باشد ولی دارای حافظه نامحدود می باشد. ☑
ج. ماشین تورینگ قادر به انجام برخی از کارهایی که یک کامپیوتر انجام می دهد نیست.
د. ماشین تورینگ مشابه اتوماتای متناهی میباشد و قادر به حل تمام مسائل می باشد.
– اتوماتای پشته ای مدل خوبی برای وسایلی است که
الف. دارای حافظه نامحدود هستند و این حافظه فقط بصورت آخرین داده ورودی اولین داده خروجی کار می کند. ☑
ب. دارای حافظه محدود هستند و این حافظه بصورت آخرین داده ورودی اولین داده خروجی کار می کند.
ج. دارای حافظه نامحدود هستند و این حافظه بصورت اولین داده ورودی اولین داده خروجی کار می کند.
د. دارای حافظه محدود هستند و این حافظه بصورت اولین داده ورودی اولین داده خروجی کار می کند.
– کدام قسمت در توصیف ماشین تورینگ بیان میکند که ماشین از هر مرحله به چه مرحله ای می رود ؟
الف. الفبای ورودی
ب. الفبای خروجی
ج. تابع انتقال ☑
د. مجموعه جانبها
– اگر ماشین در ابتدای سمت چپ رشته ورودی خود باشد و حرکت هد به سمت چپ باشد
الف. هد در همان محل باقی می ماند. ☑
ب. هد به سمت عقب حرکت می کند.
ج. هد به سمت جلو حرکت می کند.
د. به حالت رد رشته ورودی رفته و خاتمه می یابد.
– ماشین های تورینگی که برای هر ورودی حتما متوقف شوند یعنی هیچگاه در حلقه نیفتند……………….. نامیده می شوند.
الف. تصمیم گیرنده ☑
ب. تشخیص دهنده
ج. الهام گیرنده
د. خود ارجاعی
– یک ماشین نامعین را تصمیم گیرنده گویند اگر ……….
الف. دقیقا یک مسیر روی ورودی متوقف شود.
ب. حداقل یک مسیر روی ورودی متوقف شود.
ج. تمام مسیرها روی ورودی متوقف شود. ☑
د. حداکثر یک مسیر روی ورودی متوقف شود.
– با یک نوار خالی شروع به کار میکند. اگر متوقف نشود ممکن است لیستی شامل بینهایت رشته را چاپ نماید.
الف. الهام گیرنده
ب. خود ارجاعی
ج. سلف
د. پرشمارنده ☑
– کدام مورد در مورد قدرت ماشینهای تورینگ درست است؟
الف. قدرت ماشین تورینگ معمولی از قدرت ماشین تورینگ چند نواره پیشتر است.
ب. قدرت ماشین تورینگ چند نواره از قدرت ماشین تورینگ معمولی بیشتر است.
ج. قدرت ماشین تورینگ غیر قطعی از همه بیشتر است.
د. ماشین تورینگ معمولی و ماشین تورینگ چند نواره از نظر قدرت با هم معادل هستند. ☑
– مجموعه زبانهای تشخیص پذیر تورینگ تحت کدامیک از عملگرهای زیر بسته نیست؟
الف. مکمل ☑
ب. اجتماع
ج. اشتراک
د. اجتماع و اشتراک
– کدامیک از رابطه های زیر در بین کلاسهای مختلف زبان برقرار است؟
الف. مستقل از متن > تشخیص پذیر تورینگ > تصمیم پذیر ک> منظم
ب. منظم > تصمیم پذیر > مستقل از متن > تشخیص پذیر تورینگ
ج. تشخیص پذیر تورینگ > تصمیم پذیر > مستقل از متن >منظم ☑
د. تشخیص پذیر تورینگ > مستقل از متن > تصمیم پذیر > منظم
– به این دلیل بعضی از زبانها تشخیص پذیر تورینگ نیستند که……….
الف. تعداد زبانها شما را بوده و تعداد ماشین ها تورینگ ناشمارا می باشد.
ب. تعداد زبان ها از تعداد ماشین ها تورینگ شما را بیشتر است . ☑
ج. تعدا زبان ها از تعداد ماشینها تورینگ شما را کمتر است.
د. مکمل آنها تشخیص پذیر تورینگ است.
– هر زبان …………… یک زبان …………… هم هست
الف. تشخیص پذیر- تصمیم پذیر
ب. تصمیم پذیر- تشخیص پذیر ☑
ج. تصمیم ناپذیر – تشخیص ناپدیر
د. تشخیص پذیر – تشخیص پذیر مکمل
– الهام گیرنده چیست؟
الف. یک ماشین تورینگ است که به یک چایگر متصل است.
ب. یک ماشین تورینگ است که ورودی خود را نادیده گرفته و یک کپی از توصیف خودش را چاپ می کند.
ج. یک ماشین تورینگ است که ظرفیت حافظه آن محدود است.
د. یک ماشین تورینگ است که یک وسیله خارجی مجهز است که این قابلیت را دارد که مشخص کند رشته W عضو آن زبان می باشد یا خير ☑
– حافظه نامحدود – قدرت زیاد ویژگی کدام ماشین است؟
الف. آتوماتای متناهی خطی
ب. آتوماتای تورینگ ☑
ج. آتوماتای پشته ای
د. DFA
– اگر ماشین تورینگ M برای رشته های w عضو زبان دنباله محاسباتی پذیرش شونده و برای همه رشته های غیر عضو زبان دنباله محاسباتی رد شونده داشته باشد آنگاه……..
الف. L(M) تشخیص پذیر است.
ب. L(M) تصمیم پذیر است. ☑
ج. L(M) هم تصمیم ناپذیر و هم تشخیص تاپذیر است.
د. L(M) تشخیص ناپذیر است.
– مشخصه ماشین تورینگ چیست؟
الف. حافظه محدود- قدرت کم
ب. حافظه نا محدود – قدرت کم
ج. حافظه نامحدود- قدرت زیاد ☑
د. حافظه محدود – قدرت زیاد
– در هنگام کار ماشین تورینگ در هر مرحله کدامیک از اجزاء تغییر می کنند؟
الف. تابع انتقال، وضعیت فعلی نوار و محل هد.
ب. وضعیت فعلی نواره نماد فعلی نوار و محل هد. ☑
ج. حالت تابع انتقال و محل هد.
د. الفبای ورودی حالت وضعیت فعلی نوار
– وقتی یک ماشین تورینگ روی یک رشته ورودی شروع به کار میکند سه امکان مختلف به وقوع می پیوندد. ماشین ممکن است آن را بپذیرد رد کند یا در حلقه بیفتد کدامیک از جملات زیر صحیح نیست؟
الف. حلقه یعنی ماشین روی ورودی متوقف نشود.
ب. ساختارهای پذیرش و رد را ساختارهای توقف می نامند.
ج. وقتی یک ماشین روی ورودی خود در حلقه بیفتد لازم نیست مراحل یکسانی به ترتیب مشخصی دائما تکرار شوند.
د. ماشینی که هیچ گاه در حلقه نیفتد را تشخیص پذیر گویند. ☑
– چه زبان هایی را زبانهای بازگشتی برشمردنی نیز می نامند؟
الف. منظم
ب. مستقل از متن
ج. تشخیص پذیر ☑
د. تصمیم پذیر
– در یک ماشین تورینگ نامعین . اگر محاسبات N روی W را مانند یک درخت در نظر بگیریم کدامیک از جملات زیر صحیح نیست؟
الف. هر گره از درخت یک ساختار است.
ب. ریشه درخت ساختار شروع می باشد.
ج. هر شاخه از این درخت یکی از انشعابات نامعین در محاسبات را نشان می دهد.
د. پیمایش شاخه های درخت به صورت جستجوی عمقی انجام می شود. ☑
– در کدامیک از انواع ماشینهای تورینگ بر روی یک ورودی ممکن است چندین مسیر وجود داشته باشد؟
الف. تورینگ معمولی
ب. تورینگ نامعین ☑
ج. تورینگ چند نواره
د. تورینگ تصمیم ناپذیر
– اگر تا یک گرامر به فرم نرمال چامسکی باشد هر اشتقاق به طول دارای چند گام می باشد؟
الف. 9
ب. 18
ج. 17 ☑
د. 10
– کدامیک از جملات زیر صحیح است؟
الف. هر زبان تصمیم پذیر مستقل از متن هم هست.
ب. هر زبان مستقل از متن تصمیم پذیر هم هست. ☑
ج. هر زبان تشخیص پذیر تصمیم پذیر هم هست.
د. هر زبان مستقل از متن، منظم هم هست.
