سوالات آزمون کارشناسی ارشد مهندسی کامپیوتر و علوم کامپیوتر
آزمون کاشناسی ارشد سال 1384
1 - اگر ۱ , L۲ Lزبان‌هایی نامنظم روی الفبای ∑ باشند آنگاه:
1) ۲.L ۱ Lلزوماً نامنظم است. 2) )۲L-*∑ U(۱ Lلزوماً نامنظم است.
3) ۲UL ۱ Lلزوماً نامنظم است. 4) )۱L-*∑ ( و )۲L-*∑ ( لزوماً نامنظم است.
2 - یک DFA برای زبان منظم) a* )*{ λ } L = (a*(b Uعبارت است از:
3 - کدام عبارت منظم زبان زیر را توصیف می‌کند؟
{31 ≥ k ،1 ≥ n ،1 ≥ m| k2m c3b an}L=
1) (cc) * (bbb) * a* 2) a* b* b* b* c* c*
3) aa* (bbb)* bbb (cc)* cc 4) aa* bbbb* b* b* ccc* c*
4 - گرامرهای حساس به متن (context sensitive) معادل چه نوع مدلی هستند؟
1) ماشین تورینگ (Turing Machine)2) اتوماتون‌های کراندر خطی(Linear Bounded Automata)
3) اتوماتون‌های پشته‌ای (Push Down Automata) 4)اتوماتون‌های قطعی متناهی (Deterministic Finite Automata)
5 - کدام یک از گزاره‌های زیر صحیح است؟
1) { λ } U { m ≠ n | m1 n0} = { 1 n |n ≥1n 0}- *{1و0}
2) تعداد زبان‌های منظم با حروف {1و0} حداکثر شمارا است.
3) زبان {*{1و0}uwwR v | u, v, w € }
4) برای هر زبان منظم L ، یک DFA با فقط یک حالت پذیرش یکتا مثل M وجود دارد که L(M) = L .
6 - اگر m(L) تعداد حالات DFA مینیمال متناضر با زبان *{1و0}LC باشد کدام گزاره همواره درست است؟
1) m (L) = m (LR) 2) m (LR) 2m (L) ≥
3) m(LR) 2m (L) ≤ 4) m (L) ≤ min (m(L), m(LR))
7 - اگر i| W | تعداد حروف i درکلمه w باشند آنگاه کدام گزاره درمورد زبان {(1=f (|w| w |0 | | *{ 1و0}L ={w € که در آن f(n) = n mod 5 است صحیح تر است؟
1) مستقل از متن است. 2) متناهی است.
3) مستقل از متن است. 4) وابسته به متن است ولی مستقل از متن نیست.
8 - گرامر زیر را در نظر بگیرید:
G : S→ XY
X→ 0X
λ →X
Y1Y→
λ Y→
همة گزاره‌های زیر صحیح‌اند به جز:
1) L (G) مستقل از متن است. 2)w € L(G) تصمیم پذیر نیست.
3)L(G) منظم است. 4) L(G) اشتراک دو زبان مستقل از متن است.
9 - برای هر زبان محاسبه پذیر (r.e.) مثل *{1و0}L C می‌توان.....................
1) یک ماشین تورینگ T با 5 حالت طراحی کرد به طوری که L(T) = L.
2) یک ماشین تورینگ قطعی T طراحی کرد که برای هر ورودی در زمان متناهی متوقف می‌شود و L(T) = L.
3) یک ماشین تورینگ T با یک نوار حافظه متناهی طراحی کرد به طوری که L(T) = L.
4) یک ماشین تورینگ T linear bounded معرفی کرد به طوری که .L(T) = L
10 - اتوماتون یک ماشین PDA فاقد انتقال بلادرنگ (λ – transition) است. آنگاه لزوماً:
1) برای هر ورودی ماشین دقیقاًَ یک مسیر محاسبه یکتا دارد.
2) برای هر ورودی ماشین حداکثر یک مسیر محاسبه یکتا دارد.
3) زمان محاسبه هر ورودی متناهی است.
4) زبان ماشین شامل کلمه پوچ (λ) نیست.
11 - کدام گزاره نادرست است؟
1) ماشین PDA ای مثل P را می‌توان ساخت که کلیه مسیرهای محاسبه برای کلیه ورودی‌های w نامتناهی (loop) باشند.
2) ماشین PDA ای مثل P و کلمه ورودی W را می‌توان ساخت که کلیه مسیرهای محاسبه P با ورودی W متناهی و منجر به پذیزش (accept) باشند.
3) ماشین PDA ای مثل P وکلمه ورودی W را می‌توان ساخت که کلیه مسیرهای محاسبه P با ورودی W نامتناهی (loop) باشند.
4) اگر h یک حالت توقف برای یک ماشین PDA باشد، آنگاه قطعاً ماشین هیچ وقت نمی‌تواند با یک فرمان ساعت از حالت h به حالت دیگری تغییر وضعیت دهد.
12 - یک ماشین PDA با n حالت برای محاسبه کلیه ورودی‌ها حداکثر از 1+n2 سلول از حافظه پشته (stack) خود استفاده می‌کند. در این صورت کدام گزاره همواره درست نیست؟
1) برای زبان این ماشین یک گرامر منظم وجود دارد.
2) برای زبان ماشین یک ماشین nondeterministic finite automaton بدون انتقال بلادرنگ (λ – transition) وجود دارد.
3) برای زبان این ماشین یک ماشین nondeterministic finite automaton با انتقال بلادرنگ وجود دارد.
4) زبان این ماشین deterministic context free نیست.
13 - همه زبان‌های زیر مستقل از متن هستند به جز:
1)L = {a n b n c m | n ≥ 0 ,m ≥ 0} ∩ {a 2n b 2n c 2m | n ≥ 0 ,m ≥ 0}
2) n ≥ 0 ,m ≥ 0} |{a n b m c 2m ∩ 0 ,m ≥ 0} ≥ n L = {a n b 2n c m |
3) L = {a 2n b n c m | n ≥ 0 ,m ≥ 0 }
4) L = {a 2m b n c n | n ≥ 0 ,m ≥ 0}
14 - زبان Lf = {1f(n) ∕ n € N} € {1}* که در آنf : N → N تابعی صعودی است.............
1) برای هر تابع محاسبه پذیر و صعودی f منظم است. 2) برای هر انتخاب تابع f منظم است.
3) چنانچه مستقل از متن باشد حتماً منظم نیز هست. 4) برای هر تابع محاسبه پذیر صعودی f مستقل از متن است.
15 - ماشین تورینگ T در حداکثر 27 مرحله پیکربندی نهایی می‌رسد. در این صورت،............................
1) زبان ماشین T با یک عبارت منظم قابل توصیف است.
2) ورودی W وجود دارد که ماشین برای محاسبه آن حداقل 7 خانه از حافظه خود را به کار می‌برد.
3) ماشین T برای محاسبه هر ورودی حداکثر از 2 خانه از حافظه خود استفاده می‌کند.
4) هیچ ماشین PDA معادل T وجود ندارد ولی زبان ماشین T وابسته به متن است.
16 - کدام یک از زبان‌های زیر نامنظم است؟
1){a n b n (a + b)* | n ≥ 0} 2) {b* a n b n a* | n ≥ 0} 3){a* a n b n b* | n ≥ 0} 4) هر سه نامنظم است.
17 - کدام یک از دلایل زیر برای اینکه نشان دهیم زبان L منظم نیست کافی است؟
1) عدد ثابت مثل n وجود دارد به طوری که برای هر رشته | z | ≥ n , z € L داشته باشیم:
Z = uvwxy , |vx | ≠ 0, |vwx | ≤ n, Ai ≥ 0 uvi wxi y € L
2) عدد ثابت مثل n وجود دارد به طوری که برای هر رشته | z | ≥ n, z € L داشته باشیم:
z = xyw , | y | ≠ 0, | xy | ≤ n , Ai ≥ 0 xyi w € L
3) هیچ عدد ثایت مثل n وجود ندارد به طوری که برای هر رشته | z | ≥ n, z € L داشته باشیم:
z = uvwxy , | vx | ≠ 0, | vwx | ≤ n, Ai ≥ 0 uvi wxi y € L
4) هیچکدام
18 - می‌گوییم زبان Definite .L است اگر عدد k وجود داشته باشد که برای هر رشته w تعلق آن به زبان تنها وابسته به آخرین k نماد w باشد کدام گزینه نادرست است؟
مثال از زبان ( a+b )* cde :Definite که در آن k=3 است.
1) زبان‌های Definite تحت عمل اجتماع بسته هستند. 2) زبان‌های Definiteتحت عمل مکمل گیری بسته هستند.
3) هر زبان Definite با یک ماشین متناهی پذیرفته می‌شود. 4) زبان‌های Definite تحت عمل (Kleene star)* بسته هستند
19 - مجموعه‌های زیر را در نظر بگیرید:
L(PDA) :مجموعه زبان‌هایی که برای آنها(Pushdown Automata) PDA وجود دارد.
L(DPDA) :مجموعه زبان‌هایی که برای آنها (Deterministic PDA) DPDA وجود دارد
N(DPDA) :مجموعه زبان‌هایی که برای آنها DPDA وجود دارد و با خالی شدن پشته پذیرفته می‌شوند.
L(UA) :مجموعه زبان‌های مستقل از متن غیر مبهم (unambiguous context free)
L(IA):مجموعه زبان‌های مستقل از متن ذاتاً مبهم (Inherently Ambiguous)
کدام یک از نمودارهای مجموعه‌ای زیر درست است؟
20 - اتومات متناهی زیر را در نظر می‌گیریم. اتومات کمینه (minimized) مربوط دارای چند حالت خواهد بود؟
1) 3
2) 2
3) 5
4) 4
21 - δ ( q,a) = (q', X , L) , δ(q , a) = (q' , X , R) قواعد نمونة یک ماشین تورینگ می‌باشند که اگر ماشین در حالت q باشد و سر آن حرف a را روی نوار ببیند به حالت q' رفته حرفa به x عوض شده و سر ماشین به ترتیب به راست (R) و یا چپ (L) می‌رود زبان ماشین تورینگ با قواعد زیر کدام است؟4q حالت نهایی B علامت جای خالی روی نوار و ∑ = {a,b} مجموعة واژه‌‌های زبان است:
δ(q0 ,a) = (q1 , x ,R) , δ(q0 , y) =(q3 , y, R) , δ(q1 ,a ) =(q1 ,a ,R) ,δ(q1 ,y) = (q1 ,y ,R) ,δ(q1 ,b) = (q2 ,y ,L),
δ(q2 ,a) = (q2 ,a ,L),δ (q2 ,y) =(q2 ,y ,L), δ (q2 ,x) =(q0 ,x ,R), δ(q3 ,y) =(q3 ,y ,R), δ(q3 ,B) =( q4 ,B ,R)
1) | n ≥ 0} an bn} 2)≥1} an bn an | n}
3) {تعداد a ها با تعداد b ها برابر است (a + b)+ | {w € 4) هیچکدام
مهدی ارزانی
مهدی نصراله براتی
