Formaalit kielet ja automaattien teoria / syksy 2008

Harjoitus 2, viikko 38

1. Olkoon S = {a,b}. Määritellään epädeterministiset automaatit M₁ = (K₁,S,D₁,s,F₁) ja M₂ = (K₂,S,D₂,q,F₂) seuraavasti: K₁ = {s, s₁}, D₁ = {(s,a,s), (s,a,s₁), (s₁,b,s₁), (s₁,b,s), }, F₁ = {s}, K₂ = {q, q₁, q₂, q₃}, D₂ = {(q,b, q₁), (q₁,a,q₂), (q₁,b,q₃), (q₂,a,q₁), (q₃,a,q₁)}, F₂ = {q₁, q₂}.

Esitä automaatit graafin muodossa. Mitkä sanoista a, aa, aab, abab, abaa ovat

hyväksyttävissä automaatilla M₁ ja vastaavasti automaatilla M₂ ?

2. Esitä seuraavat kielet epädeterminististen tai determinististen automaattien avulla (tilagraafeina):

a) (aa*b)*b* È aa* b) ((bb È bab)*a)*

3. Esitä seuraavat kielet epädeterminististen tai determinististen automaattien avulla (tilagraafeina):

a) ((a*b*a)*b)* b) (ba È b)* È (bb È a)*

4. a) Esitä kieli (ab È aba)*a aidosti epädeterministisen automaatina avulla.

b) Muuta a)-kohdassa konstruoitu automaatti deterministiseksi luennolla

esitetyllä menetelmällä (osajoukkokonstruktio).

5. Osoita, että äärellisen automaatin hyväksymän kielen katenaatiosulkeuma

samoin kuin komplementti ovat myös äärellisen automaatin hyväksymiä kieliä.

(Lause 2, s. 16)

6. Tutki, ovatko seuraavat kielet säännöllisiä (perustelut):

a) {waw | w Î {a,b}*}

b) {w | w = w^R}