Rozšírení konečných automatů II Automaty s £-kroky
IB102 Automaty a gramatiky, 15.10.2012
1
Definice 2.46.    Nedeterministický konečný automat s f-kroky je
AA = (Q, E, 5, go? kde význam všech složek je stejný jako v definici NFA s výjimkou přechodové funkce 8. Ta je definována jako totální zobrazení ô : Q x (E U {e}) 2Q.
Rozšířená přechodová funkce
Definujeme funkci D£ : Q     2® následujícím předpisem. D£(p) je nejmenší množina X C Q taková, že platí:
• P G X,
• pokud q G X a r G S(q,e), pak také r G X.
Rozšíření funkce D£ na množiny stavů: pro Y C Q položíme
D£(Y) = (J De{q).
IB102 Automaty a gramatiky, 15.10.2012
2
Příklad - výpočet D£
IB102 Automaty a gramatiky, 15.10.2012
3
Definice rozšířené přechodové funkce 5 : Q x S* —> 2®
• S(q,e) = De(q),
• S(q,wá) = \JpeS(qw)D£(5(p,a)).
Lemma 2.47.       V přechodovém grafu automatu Ai existuje cesta
pi A ... A pm A qi A ... A qni kde m, n > 1, a £ £, právě když
/\
<?n € 5(pi,o).
Jazyk přijímaný automatem A4 s e-kroky je
L(M) — {w G S* | %o,w)nF^}
IB102 Automaty a gramatiky, 15.10.2012
Příklad - výpočet rozříšeřené přechodové funkce
pro automat s 6-kroky
IB102 Automaty a gramatiky, 15.10.2012
5
Ekvivalence automatů s e-kroky a N FA
Věta 2.48. Ke každému NFA M = (Q, E, ô, q0, F) s e-kroky existuje ekvivalentní NFA (bez e-kroků).
Důkaz. Konstrukce M = (Q, E,7, qo, G) bez e-kroků:
7(5, a) = 8{q, a) pro každé q G Q, a G S
F pokud D£(g0)nF = 0,
FU{g0} jinak.
Korektnost: Dokážeme, že pro libovolné p G Q, w G S+ platí <5(p, ty) = 7(p, w) {indukcí vzhledem k délce slova w).
Algoritmus □
IB102 Automaty a gramatiky, 15.10. 2012 6
Uzáverové vlastnosti regulárních jazyků
Věta 2.49. a 2.51. Třída regulárních jazyků je uzavřená na sjednocení, průnik, rozdíl a komplement.
Důkaz, synchronní paralelní kompozice automatů + komplement. □
Příklad. Li   =   {ať6V | 2i > j > 0}
L2   = W*.{&}* L3   =   {anbn | n > 0}
Li n L2 = ^3
Jazyk L2 je regulární, L3 není regulární      Li není regulární.
IB102 Automaty a gramatiky, 15.10.2012
7
Věta 2.52. Třída regulárních jazyků je uzavřená na zřetězení. Důkaz.
Necht Za a L2 jsou regulární jazyky, rozpoznávané NFA Mi =
(Qi, £1, <5i, qi, Fi) a M2 = (Q2, S2,52,52, F2), kde Qi n Q2 = 0.
Definujeme NFA s e-kroky TWi O 7W2 = (Qi U Q2, Si U E2, <5, gi, F2), kde
á = <5i U Ô2 U {((p, e), {q2}) I P G Fi}.
IB102 Automaty a gramatiky, 15.10.2012
8
Korektnost: Chceme dokázat L(M\ 0 M2) = L(Mi).L(M2)
D:   Necht u G L(Mi), tedy 3r G Fi splňující r G Necht v e L(M2), tedy S2(q2, v) n F2 ^ 0. Pak
5(qi,uv)=    (J    S(p,v) D S(r,v) 2 S(q2,v) = 52(q2
peS(qi,u)
Protože S2(q2, v) íl F2 ^ 0, tak 5(qltuv) f)F2^^. Tedy uv e L(Mi 0 M2).
C:
IB102 Automaty a gramatiky, 15.10.2012
Věta 2.53. Třída regulárních jazyků je uzavřená na iteraci. Důkaz.
Necht L je regulární jazyk akceptovaný NFA M = (Q, E, 5, go? F). Definujeme NFA s s-kroky M* = (Q U {p}, E, S1\p, {p}), kde p ^ Q
Sŕ = SU {((p, e), {q0}} U {((q, e), {p}) \ q G F}.
IB102 Automaty a gramatiky, 15.10.2012
Uzáverové vlastnosti regulárních jazyků - Shrnutí
IB102 Automaty a gramatiky, 15.10.2012
11
Regulární výrazy
Definice 2.58. Množina regulárních výrazů nad abecedou E, označovaná RE(Ľ), je definována induktivně takto:
1. s, 0 a a pro každé a G E jsou regulární výrazy nad E fŕzv. základní regulární výrazy).
2. Jsou-li F, F regulární výrazy nad E, jsou také (E.F),(E + F) a (E*) regulární výrazy nad E.
3. Každý regulární výraz vznikne po konečném počtu aplikací kroků 1-2.
IB102 Automaty a gramatiky, 15.10.2012
12
Každý regulární výraz E nad abecedou E popisuje (jednoznačně určuje) jazyk L (E) nad abecedou E podle těchto pravidel:
L(e) dá {e}
L(0) =' 0
L{a) = {a} pro každé a G S
L(£.F) =; L(E).L(F)
L(E + F) = L(E)UL(F)
L( E*) = L(£)*
IB102 Automaty a gramatiky, 15.10.2012
13
Příklady
IB102 Automaty a gramatiky, 15.10.2012
Ekvivalence konečných automatů a reg. výrazů
DFA
Věta 2.43
NFA
Věta 2.48
Věta 2.60. Necht E je regulární výraz.   Pak existuje konečný
automat rozpoznávající L(E).
Důkaz. Pro libovolnou abecedu £ lze zkonstruovat konečné automaty, které rozpoznávají jazyky popsané základními regulárními výrazy, tj. 0, {e} a {a} pro každé a G E. Tvrzení věty pak plyne z uzavřenosti jazyků rozpoznatelných konečnými automaty vůči operacím sjednocení, zřetězení a iteraci. □
IB102 Automaty a gramatiky, 15.10.2012
15
Příklad
IB102 Automaty a gramatiky, 15.10.2012
D FA
Věta 2.43	N FA	Věta 2.48 r
s		
NFA s s-kroky
Věta 2.62. Necht L je akceptovaný nějakým DFA, pak L je
popsatelný nějakým regulárním výrazem.
Důkaz bude podán později pomocí regulárních přechodových grafů.
Kleeneho věta 2.63. Libovolný jazyk je popsatelný regulárním výrazem právě když je rozpoznatelný konečným automatem.
Ekvivalentní formulace: Třída jazyků rozpoznatelných konečnými automaty je nejmenší třída, která obsahuje všechny konečné množiny a je uzavřena na sjednocení, zřetězení a iteraci.
IB102 Automaty a gramatiky, 15.10.2012
17