مثال ها و تمرین های نظریه محاسبات، زبان ها و ماشین ها (آتاماتا)
زبان ها، گرامرها و عبارات منظم به همراه DFA
هر مثال شامل پیاده سازی عبارت منظم، گرامر و بسته به زبان به همراه ماشین DFA، NFA یا PDA است، همچنین توضیح و ارائه زبان مربوطه به صورت یکجا کنار هم می باشد.
زبان های منظم
روی الفبای {a,b}=Σ تمام رشته هایی که ...
{w : w ∈ {a, b}*} - بدون محدودیت می توان تولید کرد؟
(a+b)*S -> aS|bS|λ
{wa : w ∈ {a, b}*} - به حرف a ختم می شوند؟
(a+b)*aS -> aS|bS|a{aw: w ∈ {a, b}*} - با حرف a شروع می شوند؟
a(a+b)*{awa: w ∈ {a,b}*} - با a شروع و با a به پایان می رسند؟
a(a+b)*aS -> aA
A -> aA|bA|a
یا
S -> Aa
A -> Aa|Ab|a
{auaava : u, v ∈ {0, 1}*} - با a شروع و خاتمه یابد و حاوی aa باشد؟
a(a+b)*aa(a+b)*aS -> aA
A -> aB|bA
B -> aC|bA
C -> aC|bC|a{w ∈ {a, b}* : na(w) <= 1} - فقط حاوی یک a (حداکثر یک a داشته) باشد؟
b*(λ+a)b*
b*(b*+ab*)
(b*+b*a)b*S -> bS|aA|λ
A -> bA|λ
{baw : w ∈ {a, b}*} - با پیشوند ba شروع می شوند؟
ba(a+b)*S -> baA
A -> aA|bA|λ
یا
S -> Sa|Sb|ba
{wau : w, u ∈ {a, b}*} - شامل زیر رشته a (حداقل یک a داشته) باشد؟
b*a(a+b)*شامل زیر رشته a نباشد؟
b*{wabu : w, u ∈ {a, b}*} - شامل زیر رشته ab باشند؟
b*a*ab(a+b)*{waaau : w, u ∈ {a, b}*} - شامل زیر رشته aaa باشند؟
(b+ab+aab)*aaa(a+b)*شامل زیر رشته aaa نباشند؟
(b+ab+aab)*(λ+a+aa){waabu : w, u ∈ {a, b}*} - شامل زیر رشته aab باشند؟
(b+ab)*a*aab(a+b)*S -> bS|aA
A -> bS|aB
B -> aB|bC
C -> aC|bC|λS -> aS|bS|aabA
A -> aA|bA|λبرعکس مثال بالا به طوری که شامل زیررشته aab نباشند؟
(b+ab)*a*S -> bS|aA|ɛ
A -> bS|aB|ɛ
B -> aB|ɛ
{w ∈ {a, b}* : nb(w) mod 2 = 1} - تعداد b ها در آن فرد باشد؟
a*b(a+ba*b)*
S -> aS|bA
A -> aA|bS|λ
{w ∈ {a, b}* : nb(w) mod 2 = 0} - تعداد b ها در آن زوج باشد؟
(a+ba*b)*a*(ba*ba*)*S -> aS|bA|λ
A -> aA|bS
{w ∈ {a, b}* : |w| mod 3 = 0} - مثال:طول رشته به عدد 3 بخش پذیر باشد؟
((a+b)(a+b)(a+b))*S -> aA|bA|λ
A -> aB|bB
B -> aS|bS
{w : w has the same number of "ab" as "ba"} یا {awa: w ∈ {a,b}*} ∪ {bwb: w ∈ {a,b}*} ∪ {a,b}
b(a*b)*+a(b*a)*+λ{w : w has EVEN number of "ab"}
(aa*bb*aa*b+b)*a*{an bm : n, m >= 0} - همواره حرف a قبل از b بیاید؟
a*b*S -> aS|A
A -> bA|λ
S -> aS|aA|λ
A -> aA|λ{an bm ck : n, m, k >= 0} - الفبای {a,b,c} که حرف a قبل از b و c بعد از b بیاید؟
a*b*c*S -> aS|A
A -> bA|B
B -> cB|λS -> aS|bA|cB|λ
A -> bA|cB|λ
B -> cB|λزبان های خطی غیر منظم
{an bn : n >= 0} - حرف a قبل از b بیاید و تعداد a و b برابر باشد؟
S -> aSb|λ{an bn : n >= 1} - حرف a قبل از b بیاید تعداد a و b برابر باشد و حداقل یک ab وجود داشته باشد؟
S -> aSb|ab
{an bn+1 : n >= 0} - حرف a قبل از b بیاید و تعداد b همواره یکی از a بیشتر باشد؟
S -> aSb|b{an b2n : n >= 0} - حرف a قبل از b بیاید و تعداد b همواره دو برابر تعداد a باشد؟
S -> aSbb|λ{a2 bn cn : n >= 0}
S -> aaA
A -> bAc|λ{an+m bm : n, m >= 0} - حرف a قبل از b بیاید و تعداد a ها مجموع تعداد a و b باشد؟
S -> aSb|C
C -> aC|λ{anbn+m : n >= 0, m >= 2} - حرف a قبل از b بیاید و تعداد b ها مجموع تعداد a و b باشد و تعداد b ها بزرگتر یا مساوی 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|λ{an bm cn : 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|λ{an bm cn+2m : n, m >= 0}
S -> aSc|A
A -> bAcc|λ
{wwR: w ∈ {a, b}*} - هر رشته با معکوسش برابر باشد و طول رشته زوج باشد (Palindrome)؟
S -> aSa|bSb|λ
{w ∈ {a, b}*: w = wR} - هر رشته با معکوسش برابر باشد؟
S -> aSa|bSb|a|b|λ
زبان های مستقل از متن
تعداد a و b برابر باشد و در هر پیشوند از رشته، تعداد a ها بزرگتر یا مساوی b ها باشند؟
S -> aSb|SS|λدر هر پیشوند از رشته، تعداد a ها بزرگتر یا مساوی b ها باشند؟ برابری تعداد a و b مهم نیست
S -> aSb|SS|aS|λ{w ∈ {a, b}* : na(w) = nb(w)} - تعداد a و b برابر باشد؟
S -> aSb|bSa|SS|λ{an bn cn : n >= 1}