Formaalit kielet ja automaattien teoria / syksy 2008

Harjoitus 4, viikko 40

1. Tarkastellaan pinoautomaattia M = (K, S, G, D, s, F), missä

K = {s, f}, F = {f}, S = {a, b}, G = {a} ja

D = {((s, a, e), (s, a)), ((s, b, e), (s, a)), ((s, a, e), (f, e)), ((f, a, a), (f, e)),

((f, b, a), (f, e))}.

a) Etsi kaikki sanan aba laskut eli transitiojonot.

b) Minkälainen on kieli L(M)? Kuvaile lyhyesti.

2. Konstruoi kielelle L = {a^mbⁿ | m < n} CF-kielioppi tai vastaava pinoautomaatti.

3. Osoita, että kieli L = {w Î {a, b, c}* | w:ssä on yhtä monta a:ta, b:tä ja c:tä} ei ole CF-kieli.

4. Osoita, että kieli L = {wcw^R | w Î {a, b}* } on deterministinen CF-kieli konstruoimalla vastaava pinoautomaatti.

5. Osoita, että kieli L = {aⁿba^mba^m+n | n ³ 1, m ³ 1} ei ole säännöllinen.

6. Konstruoi edellisessä tehtävässä määritellyn kielen hyväksyvä pinoautomaatti.