IB102 ­ úkol 5 Odevzdání: 20. 10. 2008
Vypracoval(a): UČO:
Skupina:
1. [2 body] Nechť L je jazyk nad abecedou  a w  
. Definujme následující operaci:
w/L = {u | wu  L}
Například pro L = {ab, aba, bba} platí ab/L = {, a}.
Bez využití převodu na DFA uvedťe obecný postup, kterým lze pro libovolný nedeterministický
konečný automat M bez -kroků a slovo w sestrojit automat M (bez -kroků),
pro který platí L(M ) = w/L(M). Tím dokážeme, že je třída regulárních jazyků uzavřena
na operaci w/L pro každé w. Zdůvodněte správnost své konstrukce.
IB102 ­ úkol 5 Odevzdání: 20. 10. 2008
Vypracoval(a): UČO:
Skupina:
2. [2 body] K zadanému nedeterministickému konečnému automatu zkonstruujte ekvivalentní
minimální konečný automat v kanonickém tvaru. Konstrukci zde uvedťe.
a b
 1 {2, 3, 4} {3, 4}
 2 {2, 3} {3, 4}
3  {3, 4, 5}
4 {5} {4, 5}
5