Rozšírení konečných automatů II Automaty š £-kroky
IB102 Automaty a gramatiky, 18.10.2010
1
Definice 2.46.    Nedeterministický FA s e-kroky je
M = (Q, S, ô, q0, F), kde význam vsech složek je stejný jako v definici NFA s výjimkou prechodove funkce ô.  Ta je definovaná jako totální
RozSírená prechodová funkce
Definujeme funkci D£ : Q — 2Q nasleduj íc ím předpisem. D£(p) je nejmensí množina X C Q takova, že platí:
• p G X,
• pokud q G X a r G ô (q, e), pak take r G X.
Rozs íren í funkce D£ na množiny stavu: pro Y C Q polož íme
zobrazen í ô : Q x (S U {e}) — 2Q.
q GY
IB102 Automaty a gramatiky, 18.10.2010
2
Příklad - výpočet D£
IB102 Automaty a gramatiky, 18.10.2010
3
Definice rozšírené přechodové funkce ô : Q x S* — 2Q
• ô(q,e) = D£(q),
• <5(q,wa) = UpGí(g>w) De(ô(p,a)).
Lemma 2.47. V přechodovem grafu automatu M existuje cešta pi — ... — pm — qi — ... — qn, kde m, n > 1, a G S, prave kdyZ qn G ô(pi,a).
Jazyk přijímaný automatem M š e-kroky je
L (M) = {w G S* | <5(qo, w) n F = 0}.
IB102 Automaty a gramatiky, 18.10.2010
4
Příklad - výpočet rozříšeřené přechodové funkce
pro automat š £-kroký
IB102 Automaty a gramatiky, 18.10.2010
5
Ekvivalence automatů s e-kroky a NFA
Věta 2.48. Ke každému NFA M = (Q, S, ô, q0, F) s e-kroky existuje ekvivalentní NFA (bež e-krokU).
Důkaz. Konstrukce M = (Q, S,Y,q0 , G) bež e-krokU:
Y (q, a) = S(q, a) pro každe q G Q, a G S
G = j F pokud D£(qo) n F = 0,
(F U{qo} jinak.
Korektnost:    Dokažeme, že pro libovolne p G Q, w G S+ platí
ô(p, w) = Y(p, w) (indukcí vzhledem k délce slova w).
Algoritmus
□
IB102 Automaty a gramatiky, 18.10.2010
6
Uzáverové vlastnosti regulárních jazyků
Věta 2.49. a 2.51. Tř ída regularn ích jazyků je uzavřená na sjednocení, průnik, rozd íl a komplement.
Důkaz. synchronn í paraleln í kompozice automatů + komplement. □
Pr íklad. L1   —   [aibicj | 2i > j > 0}
L2   = |a}*.{b}* L3   =   {anbn | n > 0}
Li n L2 — L3
Jazyk L2 je regularn í, L3 nen í regularn í      L1 nen í regularn í.
IB102 Automaty a gramatiky, 18.10.2010
7
Veta 2.52. Důkaz.
Třída reguiarních jazyku je uzavřena na zřetézení.
Necht Li a L2 jsou reguiarní jazyky, rozpoznavane NFA Mi =
(Qi, Si, Si, qi, Fi) a M2 = (Q2, S2, §2, Q2, F2), kde Qi n Q2 = 0.
Definujeme NFA s e-kroky Mi 0 M2 = (Qi U Q2, Si U S2, S, qi, F2),
kde
S = Si U S2 U {((p, e), {q2}) | p e Fi}.
IB102 Automaty a gramatiky, 18.10.2010
8
Korektnost: Chceme dokazat L(Mi © M2) = L(Mi).L(M2)
3:   Necht u G L(M1), tedy 3r G F splňující r G 51(q1,u). Necht v G L(M2), tedy (52(q2, v) n F2 = 0. Pak
/\ I I /\ S\ S\ -----
S(qi,uv) =    (J    5(p,v) 3 S(r,v) 3 %2,v) = Ô2(q2,v).
pG^(qi,u)
ProtoZe Č2(q2, v) n F2 = 0, tak ô(qi, uv) n F2 = 0. Tedy uv G L(Mi © M2).
C:
□
IB102 Automaty a gramatiky, 18. 10. 2010
9
Veta 2.53. Trída regularn ích jazyku je uzavřena na iteraci. Důkaz.
Necht L je regularn í jazyk akceptovany NFA M — (Q, S, ô, q0, F). Definujeme NFA s e-kroky M* — (Q U {p}, S, ô',p, {p}), kde p G Q a
ô' — ô U {((p, e), {qo}} U {((q, e), {p}) | q G F}.
□
IB102 Automaty a gramatiky, 18. 10. 2010
10
Uzáverové vlastnosti regulárních jazyků - Shrnutí
IB102 Automaty a gramatiky, 18.10.2010
11
Regulární výrazy
Definice 2.58. Množina regulárních výrazů nad abecedou E, oznacovana RE(E), je definovana induktivně takto:
1. e, 0 a a pro každe a G E jsou regularní vyrazy nad E (tzv. základní regulární výrazy).
2. Jsou-li E,F regularn í vyrazy nad E, jsou take (E.F), (E + F) a (E*) regularn í vyrazy nad E.
3. Kazdy regularn í vyraz vznikne po koneCnem poCtu aplikac í kroku 1-2.
IB102 Automaty a gramatiky, 18.10.2010
12
Kazdy regularn í vyraz E nad abecedou E popisuje (jednoznaCne urCuje) jazyk L(E) nad abecedou E podle techto pravidel:
L(e)	def	{e}
L(0)	def	0
L(a)	def	{a} pro kazde a G E
L( E.F)	def	L(E).L(F)
L( E + F)	def	L(E) U L(F)
L( E *)	def	L(E )*
IB102 Automaty a gramatiky, 18. 10. 2010
13
Príklady
IB102 Automaty a gramatiky, 18.10.2010
14
Ekvivalence konečných automatů a reg. výrazů
r
DFA
Veta 2.43
r
NFA
Veta 2.48
r
NFA s e-kroky
Veta 2.60. Necht E je regularn í vyraz.   Pak existuje konecny
automat rozpoznavaj íc í L(E).
Důkaz. Pro libovolnou abecedu S lze zkonstruovat koneCne automaty, ktere rozpoznavaj í jazyky popsane zakladn ími regularn ími vyrazy, tj. 0, {e} a {a} pro kazde a G S. Tvrzen í vety pak plyne z uzavřenosti jazyku rozpoznatelnych konecnymi automaty vuci operac ím sjednocen í, zretezen í a iteraci. □
IB102 Automaty a gramatiky, 18.10.2010
15
Příklad
IB102 Automaty a gramatiky, 18.10.2010
16
r
DFA
Veta 2.43
r
NFA
Veta 2.48
r
NFA s e-kroký
Vetá 2.62. Necht L je akceptovaný nejakým DFA, pak L je
popsatelný nejakým regularn ím výrazem.
DUkáz bude podan pozdeji pomoc í regularn ích prechodových grafu.
Kleeneho vetá 2.63. Libovolný jazýk je popsatelný regularn ím výrazem prave kdýž je rozpoznatelný konecným automatem.
Ekviválentní formuláce: Třída jazýku rozpoznatelných konecnými automatý je nejmens í trída, ktera obsahuje vsechný konecne množiný a je uzavřena na sjednocen í, zretezen í a iteraci.
IB102 Automatý a gramatiký, 18. 10. 2010
17