Formaalit kielet ja automaattien teoria / syksy 2008

Harjoitus 1 (viikko 37)

1. Osoita, että seuraavat väitteet pitävät paikkansa:

a) {e}^* = {e}.

b) Jos a ja b ovat eri symboleita, niin {a,b}^* = {a}^*({b}{a}^*)^*.

2. Anna joitakin esimerkkejä aakkoston S = {a,b} sanoista, jotka kuuluvat ja jotka eivät kuulu seuraaviin kieliin:

a) {w | w = uu^Ru, u Î SS},

b) {w | ww = www},

3. Olkoon S = {a, b}. Kirjoita säännöllinen ilmaisu, joka esittää

a) kaikkia niitä S*:n sanoja, joissa on korkeintaan kaksi a:ta,

b) kaikkia niitä S*:n sanoja, joissa on parillinen määrä a:ta,

4. Minkälaisia sanoja kuuluu seuraavien säännöllisten ilmaisujen esittämiin kieliin.

Esitä kyseiset säännölliset ilmaisut yksinkertaisemmassa muodossa:

a) Æ^*Èa^*È b^*È(aÈb)^*

b) ((a^*b^*)^*(b^*a^*)^*)^*

5. Mitä kieltä esittää säännöllinen ilmaisu (((a^*a)b) Èb) ?

6. Mitkä seuraavista väitteistä ovat tosia?

a) baa Î a^*b^*a^*b^*

b) b^*a^*Ç a^*b^* = a^*È b^*

c) a^*b^*Ç b^*c^* = Æ

d) abcd Î (a(cd)^*b)^*

7. Konstruoi deterministiset äärelliset automaatit, jotka hyväksyvät seuraavat aakkoston {a,b} kielet:

a) {w | jokaista kirjainta b sanassa w edeltää välittömästi a},

b) {w | w:llä on osasanana abb}.