M:
a
b
b
f
a
s
Otázka:
ab Î L(M) ?
Otázka:
L(M) = Æ ?
Odpověď: NE,
protože s je ukončující
Odpověď: ANO,
protože sab |–* f, f Î F
1. qa’ ® f; q Î Q; a’ Î S: sb ® f, fa ® f
Q1 = {f} È
{s, f} = {f, s} … s je ukončující
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