M:
a
b
b
f
a
s
Otázka: ab Î L(M) ?
sab
Otázka: L(M) = Æ ?
Odpověď: NE, protože s je ukončující
Odpověď: ANO, protože sab |–* f, f Î F
Q0 = {f}
1. qa’ ® f; q Î Q; a’ Î S: sb ® f, fa ® f
Q1 = {f} È {s, f} = {f, s} … s je ukončující
|– sb
|– f, f Î F
, ...
Rozhodnutelné problémy: Příklad
Otázka: Je L(M) konečný?
Odpověď: NE, protože existuje z Î L(M), k £ |z| < 2k
Î L(M) , ...
 k = Card(Q) = 2
Všechny řetězce z Î S*: 2 £ |z| < 4: aa, bb, ab
24/26