Formaalit kielet ja automaattien teoria / syksy 2008

Harjoitus 5, viikko 41

1. Konstruoi pinoautomaatti, joka hyväksyy kielen L = {a^mbⁿ | m £ n £ 2m}.

2. Minkälainen on kieliopin G = (V, S, R, S), missä

V = {S, (, ), [, ]}, S = {(, ), [, ]}, R = {S ® e, S ® SS, S ® [S], S ® (S)},

generoima kieli? Konstruoi pinoautomaatti, joka hyväksyy saman kielen.

Kertausta:

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

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

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

c) kaikkia niitä S*:n sanoja, joissa on täsmälleen kaksi osasanan ab esiintymää.

4. Olkoon L on akkoston S kieli. Määritellään kielen L ns. alkuosakieli Pref(L) seuraavasti: Pref(L) koostuu kaikista kielen L sanojen alkuosista, ts.

Pref(L) = {w Î S* | on olemassa sellainen sana u Î S*, että wu Î L}.

Jos L = (abb È a)*, niin mikä on sen alkuosakieli Pref(L) ?

5. Osoita, että jos kieli L on säännöllinen, niin myös sen alkuosakieli Pref(L) on

säännöllinen. (Vihje: äärellisen automaatin avulla)

6. Olkoon L = {ww’ | w Î {a,b}*}, missä w’ on saatu w:stä siten, että jokaisen a:n paikalla on b ja kääntäen jokaisen b:n paikalla on a. Siis esimerkiksi sanat abba ja aabaabbabb ovat kielen L sanoja. Osoita, että kieli L ei ole säännöllinen