نظریه زبانها و ماشینها

زبان های بازگشتی

در ریاضیات، منطق و علوم کامپوتر، زبان بازگشتی یک نوع زبان صوری است که همچنین بازگشتی، تصمیم پذیر یا تصمیم پذیر بازگشتی نامیده می شود.کلاس تمامی زبان های بازگشتی غالبا" R نامیده می شود، با اینکه این نام برای کلاس RP نیز استفاده می شود.

این نوع از زبان به طور واضحی از سلسله مراتب چامسکی(Chomsky hierarchy) جا مانده است.

تعاریف:

دو تعریف برابر و اصلی برای مفهوم زبان بازگشتی وجود دارد:

1- یک زبان صوری بازگشتی یک زیر مجموعه بازگشتی(recursive subset)در مجموعه تمامی کلمات ممکن بر روی الفبای زبان است.

2- یک زبان بازگشتی یک زبان صوری است که برایش ماشین تورینگی وجود دارد که، هنگامی که با یک رشته ورودی مواجه می گردد، متوقف می شود و اگر رشته در زبان موجود باشد آن را می پذیرد، در غیر این صورت متوقف می گردد و آن رشته را نمی پذیرد. ماشین تورینگ همیشه متوقف می گردد: این ماشین به عنوان تصمیم پذیر شناخته می شود.

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

خواص بسته بودن:

زبان های بازگشتی برروی اعمال زیر بسته اند.یعنی، اگر زبان L و زبان P هر دو بازگشتی باشند، در نتیجه زبان های زیر نیز بازگشتی اند:

- ستاره L

- اتصال L وP

- اجتماع L وP

- اشتراک L وP

- اختلاف L وP

محمدحسین حاج کاظمی پنج‌شنبه 11 خرداد‌ماه سال 1385 ساعت 04:32 ب.ظ

0 نظر

میان ترم گذشته

امتحان میان ترم گذشته نظریه زبانها در لینک زیر می باشد:

http://finiteautomata.tripod.com/sitebuildercontent/sitebuilderfiles/lastmidterm.swf

احمد بزرگی فرد

امیر عبدالحمیدی دوشنبه 8 خرداد‌ماه سال 1385 ساعت 05:05 ب.ظ

0 نظر

سوالات آزمون کارشناسی ارشد مهندسی کامپیوتر و علوم کامپیوتر

برای دریافت نسخه اصلی سوالات کارشناسی ارشد از لینک زیر استفاده کنید

http://finiteautomata.tripod.com/sitebuildercontent/sitebuilderfiles/kaeshenasiearshad.pdf

مهدی جمعه 5 خرداد‌ماه سال 1385 ساعت 10:20 ب.ظ

0 نظر

سوالات آزمون کارشناسی ارشد مهندسی کامپیوتر و علوم کامپیوتر

آزمون کاشناسی ارشد سال 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| ^k²^m c³b aⁿ}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 ⁿ0} = { 1 ⁿ |n ≥1ⁿ0}- ^*{1و0}

2) تعداد زبان‌های منظم با حروف {1و0} حداکثر شمارا است.

3) زبان {^*{1و0}uww^R v | u, v, w € }

4) برای هر زبان منظم L ، یک DFA با فقط یک حالت پذیرش یکتا مثل M وجود دارد که L(M) = L .

6 - اگر m(L) تعداد حالات DFA مینیمال متناضر با زبان ^*{1و0}LC باشد کدام گزاره همواره درست است؟

1) m (L) = m (L^R) 2) ^{m (LR)} 2m (L) ≥

3) ^m(LR)2m (L) ≤ 4) m (L) ≤ min (m(L), m(L^R))

7 - اگر _i| W | تعداد حروف i درکلمه w باشند آنگاه کدام گزاره درمورد زبان {(₁=f (|w| w |₀ | | ^*{ 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 حالت برای محاسبه کلیه ورودی‌ها حداکثر از ¹⁺ⁿ2 سلول از حافظه پشته (stack) خود استفاده می‌کند. در این صورت کدام گزاره همواره درست نیست؟

1) برای زبان این ماشین یک گرامر منظم وجود دارد.

2) برای زبان ماشین یک ماشین nondeterministic finite automaton بدون انتقال بلادرنگ (λ – transition) وجود دارد.

3) برای زبان این ماشین یک ماشین nondeterministic finite automaton با انتقال بلادرنگ وجود دارد.

4) زبان این ماشین deterministic context free نیست.

13 - همه زبان‌های زیر مستقل از متن هستند به جز:

1)L = {aⁿ bⁿc ^m| n ≥ 0 ,m ≥ 0} ∩ {a ²ⁿ b ²ⁿ c ^2m | n ≥ 0 ,m ≥ 0}

2) n ≥ 0 ,m ≥ 0} |{a ⁿ b ^m c ^2m ∩ 0 ,m ≥ 0} ≥ n L = {a ⁿ b ²ⁿ c ^m |

3) L = {a ²ⁿ b ⁿ c ^m | n ≥ 0 ,m ≥ 0 }

4) L = {a ^2m b ⁿ c ⁿ | n ≥ 0 ,m ≥ 0}

14 - زبان L_f = {1^f(n)∕ n € N} € {1}^* که در آنf : N → N تابعی صعودی است.............

1) برای هر تابع محاسبه پذیر و صعودی f منظم است. 2) برای هر انتخاب تابع f منظم است.

3) چنانچه مستقل از متن باشد حتماً منظم نیز هست. 4) برای هر تابع محاسبه پذیر صعودی f مستقل از متن است.

15 - ماشین تورینگ T در حداکثر 2⁷ مرحله پیکربندی نهایی می‌رسد. در این صورت،............................

1) زبان ماشین T با یک عبارت منظم قابل توصیف است.

2) ورودی W وجود دارد که ماشین برای محاسبه آن حداقل 7 خانه از حافظه خود را به کار می‌برد.

3) ماشین T برای محاسبه هر ورودی حداکثر از 2 خانه از حافظه خود استفاده می‌کند.

4) هیچ ماشین PDA معادل T وجود ندارد ولی زبان ماشین T وابسته به متن است.

16 - کدام یک از زبان‌های زیر نامنظم است؟

1){a ⁿ b ⁿ (a + b)^* | n ≥ 0} 2) {b^* a ⁿ b ⁿ a^* | n ≥ 0} 3){a^* a ⁿ b ⁿ b^* | n ≥ 0} 4) هر سه نامنظم است.

17 - کدام یک از دلایل زیر برای اینکه نشان دهیم زبان L منظم نیست کافی است؟

1) عدد ثابت مثل n وجود دارد به طوری که برای هر رشته | z | ≥ n , z € L داشته باشیم:

Z = uvwxy , |vx | ≠ 0, |vwx | ≤ n, Ai ≥ 0 uvⁱ wxⁱ y € L

2) عدد ثابت مثل n وجود دارد به طوری که برای هر رشته | z | ≥ n, z € L داشته باشیم:

z = xyw , | y | ≠ 0, | xy | ≤ n , Ai ≥ 0 xyⁱ w € L

3) هیچ عدد ثایت مثل n وجود ندارد به طوری که برای هر رشته | z | ≥ n, z € L داشته باشیم:

z = uvwxy , | vx | ≠ 0, | vwx | ≤ n, Ai ≥ 0 uvⁱ wxⁱ 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) می‌رود زبان ماشین تورینگ با قواعد زیر کدام است؟₄q حالت نهایی B علامت جای خالی روی نوار و ∑ = {a,b} مجموعة واژه‌‌های زبان است:

δ(q₀ ,a) = (q₁ , x ,R) , δ(q₀ , y) =(q₃ , y, R) , δ(q₁ ,a ) =(q₁ ,a ,R) ,δ(q₁ ,y) = (q₁ ,y ,R) ,δ(q₁ ,b) = (q₂ ,y ,L),

δ(q₂ ,a) = (q₂ ,a ,L),δ (q₂ ,y) =(q₂ ,y ,L), δ (q₂ ,x) =(q₀ ,x ,R), δ(q₃ ,y) =(q₃ ,y ,R), δ(q₃ ,B) =( q₄ ,B ,R)

1) | n ≥ 0} aⁿ bⁿ} 2)≥1} aⁿ bⁿaⁿ | n}

3) {تعداد a ها با تعداد b ها برابر است (a + b)+ | {w € 4) هیچکدام

مهدی ارزانی

مهدی نصراله براتی

مهدی جمعه 5 خرداد‌ماه سال 1385 ساعت 10:18 ب.ظ

0 نظر

زبان های صوری

در ریاضیات، منطق و علوم کامپوتر، زبان صوری یک مجموعه از کلمات (رشته های کاراکتری) با طول متناهی است که از برخی الفباهای متناهی مشتق می گردد، و نظریه علمی که مرتبط با این مفاهیم است به عنوان نظریه زبان صوری شناخته می شود.

یک الفبا ممکن است {a,b} ،و رشته بر روی آن ababba باشد.یک زبان نمونه بر روی این الفبا، که دارای رشته عنوان شده است، ممکن است مجموعه تمام رشته های باشد که شامل علائم a و b با تعداد مساوی است.

رشته تهی (رشتهای با طول صفر) رشته با معنا تلقی می گردد و با علام $e$ , $ε$ , $Λ$ . نمایش داده می شود. از آن جایی که الفبا یک مجموعه متناهی است وهر عبارت دارای طول محدود است، زبان ممکن است دارای رشته های عضو نامحدود باشد.

سوالی که اغلب در مورد زبان های صوری پرسیده می شود این است " آیا یک عبارت داده شده به زبان تعلق دارد یا خیر؟" ، که جواب آن، بحث مورد برسی نظریه محاسبات و نظریه پیچیدگی است

چند مثال از زبان های صوری:

1- مجموعه رشته های تولید شده بر روی a و b .

2- مجموعه {a^n}،n یک عدد اول است.

3- زبانی متناهی مانند a،aa،bba .

4- مجموعای از برنامه های یک زبان برنامه نویسی که از نظر نحوی صحیح می باشند.

5- مجموعای از ورودی ها که ماشین تورینگ خاصی بر روی آن متوقف می گردد.

یک زبان صوری به وسیله راه های مختلفی مشخص می گردد، از جمله:

1- رشته هایی که توسط گرام های صوری تولید می شوند.

2- رشته هایی که توسط عبارات منظم تولید می شوند

3- رشته هایی که توسط برخی ماشین ها، مانند ماشین تورینگ یا ماشین حالت متناهی پذیرفته می شوند.

4- آن دسته از سوالات بله/ خیر که جوابشان بله است.

http://en.wikipedia.org/wiki/Formal_language