amoozesh.org
amoozesh.orgPersian Tutorials
ورود
ایجاد: 1398/9/8 00:08 - ویرایش: 1398/11/27 03:39
A A

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

زبان ها، گرامرها و عبارات منظم به همراه 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

{w ∈ {a, b}* : na(w) <= 1} - فقط حاوی یک a (حداکثر یک a داشته) باشد؟

S -> bS|aA|λ A -> bA|λ

{baw : w ∈ {a, b}*} - با پیشوند ba شروع می شوند؟

S -> baA A -> aA|bA|λ یا S -> bA A -> aB B -> aB|bB|λ یا S -> Sa|Sb|ba

{wabu : w, u ∈ {a, b}*} - شامل زیر رشته ab باشند؟

شامل زیر رشته aaa نباشند؟

(b+ab+aab)*(λ+a+aa)

{waaau : w, u ∈ {a, b}*} - شامل زیر رشته aaa باشند؟

(b+aab+ab)*aaa(a+b)*

{waabu : w, u ∈ {a, b}*} - شامل زیر رشته aab باشند؟

(a+b)*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 -> aS|bA|λ A -> aS|bB|λ B -> bB|λ

{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 ها در آن زوج باشد؟

S -> aS|bA|λ A -> aA|bS(a+ba*b)*

{w ∈ {a, b}* : |w| mod 3 = 0} - مثال:طول رشته به عدد 3 بخش پذیر باشد؟

S -> aA|bA|λ A -> aB|bB B -> aS|bS((a+b)(a+b)(a+b))*

{w : w has the same number of "ab" as "ba"}

{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|λ

تعداد 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|λ

{wwR: w ∈ {a, b}*} - هر رشته با معکوسش برابر باشد و طول رشته زوج باشد (Palindrome

S -> aSa|bSb|λ

{w ∈ {a, b}*: w = wR} - هر رشته با معکوسش برابر باشد؟

S -> aSa|bSb|a|b|λ