زبان های بازگشتی برشمردنی
در ریاضیات، منطق و علوم کامپوتر، زبان بازگشتی برشمردنی یک نوع زبان صوری است که تا حدی تصمیم پذیر یا تصمیم پذیر تورینگ نیز نامیده می شود.این نوع زبان در سلسله مراتب زبان های صوری چامسکی با عنوان زبان نوع صفر شناخته می گردد.کلاس زبان های بازگشتی برشمردنی RE نامیده می شود.
تعاریف:
سه تعریف برابر و اصلی برای مفهوم زبان بازگشتی وجود دارد:
1- یک زبان صوری بازگشتی یک زیر مجموعه بازگشتی( recursively enumerable subset ) در مجموعه تمامی کلمات ممکن بر روی الفبای زبان است.
2- یک زبان بازگشتی یک زبان صوری است که برایش ماشین تورینگی(یا تابع قابل محاسبه دیگری) وجود دارد که تمامی رشته های معتبر زبان راشمارش می کند. توجه داشته باشید که اگر زبان نا متناهی باشد، از آن جائیکه میتوانیم بررسی کنیم که آیا رشته تولید شده برای عدد n ، قبلا" برای عددی کوچکتر از n تولید شده یا نه، الگوریتم شمارش کننده می تواند به گونه ای انتخاب گردد که از تکرار جلوگیری کند. اگر رشته قبلا" تولید شده بود به جای ورودی n+1 از خروجی استفاده کنید(به صورت باز گشتی) ،اما مجددا" بررسی کنید که آیا جدید است یا نه.
3- یک زبان بازگشتی یک زبان صوری است که برایش ماشین تورینگی وجود دارد که، هنگامی که با هر رشته ورودی موجود در زبان مواجه می گردد، متوقف می شود و رشته را می پذیرد، ماشین تورینگ مورد بحث هنگام مواجه با رشته ای که در داخل زبان نیست ممکن است متوقف شود و رشته را نپذیرد یا برای همیشه در حلقه بیا فتد.
تمامی زبان های منظم، مستقل از متن، حساس به متن و بازگشتی، بازگشتی برشمردنی هستند.
RE و مکملش (co-RE) پایه سلسله مراتب حسابی (arithmetical hierarchy ) را تشکیل می دهند.
خواص بسته بودن:
زبان های بازگشتی برروی اعمال زیر بسته اند.یعنی، اگر زبان L و زبان P هر دو بازگشتی باشند، در نتیجه زبان های زیر نیز بازگشتی اند:
- ستاره L
- اتصال L وP
- اجتماع L وP
- اشتراک L وP
توجه کنید که زبان های بازگشتی برشمردنی بر روی اعمال مکمل گیری و تفاضل بسته نیستند.
http://en.wikipedia.org/wiki/Recursively_enumerable_language
موادامتحانی وضرایب رشته های دوره کارشناسی ارشد کامپیوتر
علوم کامپیوتر
1.زبان عمومی و تخصصی,2.دروس پایه (ریاضی1, 2,آمارو احتمال, مبانی کامپیوتر), 3. ریاضیات گسسته,4.ساختمان داده هاو الگوریتمها, 5. اصول سیستمهای کا مپیوتری, 6. نظریه اتوماتاو زبانها, 7. آنالیزعددی.
ضرایب به ترتیب دروس:
(2, 6, 3, 3, 3, 3, 3)
********
مجموعه مهندسی فناوری اطلاعات it
1. تجارت الکترونیکی 2. سیستمهای چندرسانهای
3.مدیریت سیستمهای اطلاعاتی
4.امنیت اطلاعات5.شبکه‌های کامپیوتری
6.مهندسی فناوری اطلاعات( it )
1. زبان تخصصی, 2.دروس مشترک (ساختمانهای گسسته,ساختمانهای داده ها,طراحی الگوریتم, مهندسی نرم‌افزار, شبکه‌ها ی کامپیوتری) ,3.اصول و مبا نی مدیریت,4.اصول طرا حی پایگاه داده‌ها,5.هوش مصنوعی,6 .سیستمها ی عامل,7.معماری کامپیوتر.
ضرایب به ترتیب دروس:
1.تجارت الکترونیکی(1, 2, 1, 1, 1, 1, 0)
2.سیستمهای چندرسانهای(1, 2, 1, 1, 1, 1, 0)
ه3.مدیریت سیستمهای ا طلاعاتی(1, 2, 2, 1, 1, 1, 0)
4.امنیت اطلاعات(1, 2, 0, 1, 1, 1, 1)
5.شبکه‌های کامپیوتری(1, 2, 0, 1, 1, 1, 1)
6.ضرایب همانندگرایش تجارت الکترونیکی
********
مجموعه مهندسی‌کامپیوتر
1. معماری کامپیوتر
2. هوش مصنوعی
3. نرم‌افزار
1.زبان عمومی وتخصصی(انگلیسی) , 2.ریاضیات(ریاضیات مهندسی,آمارواحتمالات,محاسبات‌عددی , ساختمانهای‌گسسته ), 3. دروس مشترک (ساختمان داده ها,نظریه ز بان‌هاوماشین‌ها,مدارهای‌منطقی,معماری‌کامپیوتر,سیستم عامل), 4 .دروس تخصصی معماری کامپیوتر (مدارهای الکتریکی, vlsi ,الکترونیک‌دیجیتال,انتقال داده) , 5 .دروس تخصصی هوش مصنوعی (مدارهای‌الکتریکی,طراحی الگوریتمها,هوش مصنوعی), 6.درو س تخصصی نرم‌افزار(کامپایلر,زبانهای برنامه‌سازی,طراحی الگوریتم, پایگاه داده).
ضرایب به ترتیب دروس:
1.معماری‌کامپیوتر(1, 2, 4, 2, 0, 0)
2. هوش مصنوعی(1, 2, 4, 0, 2, 0)
3.نرم‌افزار(1, 2, 4, 0, 0, 2 )
توجه: این اطلاعات مربوط به آزمون کارشناسی ارشد سال ۸۴ می باشد.
زبان های بازگشتی
در ریاضیات، منطق و علوم کامپوتر، زبان بازگشتی یک نوع زبان صوری است که همچنین بازگشتی، تصمیم پذیر یا تصمیم پذیر بازگشتی نامیده می شود.کلاس تمامی زبان های بازگشتی غالبا" R نامیده می شود، با اینکه این نام برای کلاس RP نیز استفاده می شود.
این نوع از زبان به طور واضحی از سلسله مراتب چامسکی(Chomsky hierarchy) جا مانده است.
تعاریف:
دو تعریف برابر و اصلی برای مفهوم زبان بازگشتی وجود دارد:
1- یک زبان صوری بازگشتی یک زیر مجموعه بازگشتی(recursive subset)در مجموعه تمامی کلمات ممکن بر روی الفبای زبان است.
2- یک زبان بازگشتی یک زبان صوری است که برایش ماشین تورینگی وجود دارد که، هنگامی که با یک رشته ورودی مواجه می گردد، متوقف می شود و اگر رشته در زبان موجود باشد آن را می پذیرد، در غیر این صورت متوقف می گردد و آن رشته را نمی پذیرد. ماشین تورینگ همیشه متوقف می گردد: این ماشین به عنوان تصمیم پذیر شناخته می شود.
تمامی زبان های بازگشتی بازگشتی برشمردنی نیز هستند. تمامی زبان های منظم، مستقل از متن وحساس به متن زبان های بازگشتی می باشند.
خواص بسته بودن:
زبان های بازگشتی برروی اعمال زیر بسته اند.یعنی، اگر زبان L و زبان P هر دو بازگشتی باشند، در نتیجه زبان های زیر نیز بازگشتی اند:
- ستاره L
- اتصال L وP
- اجتماع L وP
- اشتراک L وP
- اختلاف L وP
میان ترم گذشته
امتحان میان ترم گذشته نظریه زبانها در لینک زیر می باشد:
http://finiteautomata.tripod.com/sitebuildercontent/sitebuilderfiles/lastmidterm.swf
احمد بزرگی فرد
سوالات آزمون کارشناسی ارشد مهندسی کامپیوتر و علوم کامپیوتر
برای دریافت نسخه اصلی سوالات کارشناسی ارشد از لینک زیر استفاده کنید
http://finiteautomata.tripod.com/sitebuildercontent/sitebuilderfiles/kaeshenasiearshad.pdf
سوالات آزمون کارشناسی ارشد مهندسی کامپیوتر و علوم کامپیوتر
آزمون کاشناسی ارشد سال 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) هیچکدام
مهدی ارزانی
مهدی نصراله براتی