amoozesh.org
amoozesh.orgPersian Tutorials
ورود
ایجاد: 1398/9/8 00:08 - ویرایش: 1398/10/29 13:52

مثال ها و تمرین های نظریه محاسبات، زبان ها و ماشین ها (آتاماتا)

زبان ها، گرامرها و عبارات منظم به همراه DFA

هر مثال شامل پیاده سازی عبارت منظم، گرامر و بسته به زبان به همراه ماشین DFA، NFA یا PDA است، همچنین توضیح و ارائه زبان مربوطه به صورت یکجا کنار هم می باشد.

نکته مهم **: برای مشاهده جواب هر تمرین بر روی آن مثال یا تمرین کلیک راست کنید.

زبان های منظم

روی الفبای {a,b}=Σ تمام رشته هایی که ...

مثال: بدون محدودیت می توان تولید کرد؟

L = {w : w ∈ {a,b}*}(a+b)*S -> aS|bS|λ

تمرین: به حرف a ختم می شوند؟

L = {wa : w ∈ {a,b}*}(a+b)*aS -> aS|bS|a

تمرین: با حرف a شروع می شوند؟

L={aw: w ∈ {a,b}*}a(a+b)*

مثال: تعداد b ها در آن فرد باشد؟

L={w ∈ {a,b}*: nb(w) mod 2 = 1}a*b(a+ba*b)* یا a*ba*(ba*ba*)*S -> aS|bA A -> aA|bS|λ

مثال: فقط حاوی یک a (حداکثر یک a داشته) باشد؟

L={w ∈ {a,b}*: na(w) <= 1}S -> bS|aA|λ A -> bA|λ

تمرین: با پیشوند ba شروع می شوند؟

L={baw: w ∈ {a,b}*} یا L={ba{a,b}*}ba(a+b)* یا ba(a*b*)*S -> baA A -> aA|bA|λ یا S -> bA A -> aB B -> aB|bB|λ یا S -> Sa|Sb|ba

مثال: شامل زیر رشته aab باشند؟

L={waabu: w,u ∈ {a,b}*}(a+b)*aab(a+b)*S -> bS|aA A -> bS|aB B -> aB|bC C -> aC|bC|λ

تمرین: تمام رشته های الفبای {0,1} که شامل زیررشته 110 نباشند؟

(0+10)*1*S -> 0S|1A|λ A -> 0S|1B|λ B -> 1B|λ

مثال: کلیه رشته های الفبای {0,1} که دارای تعداد زوج 1 باشند؟

L={w ∈ {0,1}* : n1(w) mod 2=0}S -> 0S|1A|λ A -> 0A|1S(0+10*1)*

تمرین: با a شروع و با a به پایان می رسند؟

L={awa: w ∈ {a,b}*}a(a+b)*aS -> aA A -> aA|bA|a یا S -> Aa A -> Aa|Ab|a

مثال:طول رشته به عدد 3 بخش پذیر باشد؟

L={w ∈ {a,b}* : |w| mod 3 = 0}S -> aA|bA|λ A -> aB|bB B -> aS|bS((a+b)(a+b)(a+b))*

تمرین: الفبای {0,1} که تعداد 01 ها و 10 ها با هم برابرند؟

مثال: تعداد زوج زیر رشته ab را بپذیرد؟

(aa*bb*aa*b+b)*(λ+aa*)

تمرین: حرف a قبل از b بیاید؟

L = {anbm : n,m >= 0}a*b*S -> aS|A A -> bA|λ S -> aS|aA|λ A -> aA|λ

مثال: الفبای {a,b,c} که حرف a قبل از b و c بعد از b بیاید؟

{anbmck : n,m,k >= 0}S -> aS|A A -> bA|B B -> cB|λS -> aS|bA|cB|λ A -> bA|cB|λ B -> cB|λ

زبان های مستقل از متن

تمرین: حرف a قبل از b بیاید و تعداد a و b برابر باشد.

L = {anbn : n >= 0}S -> aSb|λ

مثال: حرف a قبل از b بیاید و تعداد b همواره یکی از a بیشتر باشد.

L = {anbn+1: n >= 0}S -> bA A -> aAb|λ

تمرین: حرف a قبل از b بیاید و تعداد a ها مجموع تعداد a و b باشد؟

L = {an+mbm : n,m >= 0}S -> aSb|C C -> aC|λ

مثال: حرف a قبل از b بیاید و تعداد b ها مجموع تعداد a و b باشد و تعداد b ها بزرگتر یا مساوی 2 باشد؟

L = {anbn+m : n >= 0, m >= 2}S -> aSb|A A -> aA|bbS ->

گرامر زبان {anbncm : n, m >= 0} چیست؟

S -> Sc|A A -> aAb|λ

گرامر زبان {anbmcm : n, m >= 0} چیست؟

S -> aS|A A -> bAc|λ

گرامر زبان {anbmcn : n, m >= 0} چیست؟

S -> aSc|A A -> bA|λ

گرامر زبان {an bm cn+m : n, m >= 0} چیست؟

S -> aSc|A A -> bSc|λ

گرامر زبان {an bm ck : k > n+m} چیست؟

S -> aSc|A A -> bSc|B B -> Bc|c

گرامر زبان {am+k bm ck : m, k >= 0} چیست؟

S -> aSc|A A -> aSb|λ

گرامر زبان {an bn+k ck : n, k >= 0} چیست؟

S -> AB A -> aAb|λ B -> bBc|λ

گرامر زبان {anbmcn+2m : n, m >= 0} چیست؟

S -> aSc|A A -> bAcc|λ

تعداد a و b برابر باشد و در هر پیشوند از رشته، تعداد a ها بزرگتر یا مساوی b ها باشند؟

S -> aSb|SS|λ

در هر پیشوند از رشته، تعداد a ها بزرگتر یا مساوی b ها باشند؟ برابری تعداد a و b مهم نیست

S -> aSb|SS|aS|λ

تعداد a و b برابر باشد.

L = {w ∈ {a,b}* : na(w) = nb(w)}S -> aSb|bSa|SS|λ

هر رشته با معکوسش برابر باشد و طول رشته زوج باشد (Palindrome

L = {WWR: W ∈ {a,b}*}S -> aSa|bSb|λ

هر رشته با معکوسش برابر باشد؟

L = {W ∈ {a,b}*: W = WR}S -> aSa|bSb|a|b|λ