Rozšíření konečných automatů II Automaty s c-kroky
IB102 Automaty a gramatiky, 14.10.2019
1/19
Definice 2.46. Nedeterministický konečný automat s č-kroky je
M = (Q, Z, S, q0, F), kde význam všech složek je stejný jako v definici N FA s výjimkou přechodové funkce S. Ta je definována jako totální zobrazení í:Qx(Iu {e}) -> 2°.
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í:
■ peX,
■ pokud q e X a r e 5(q, e), pak také r e X. Rozšíření funkce D£ na množiny stavů: pro Y c Q položíme
De{Y)= U
IB102 Automaty a gramatiky, 14.10.2019
2/19
Příklad - výpočet Dt
IB102 Automaty a gramatiky, 14.10.2019
3/19
Definice rozšířené přechodové funkce 5 : Q x Z* -> 2° ■ ô(q,s) = D£(q), mS{q,wa) = {Jp€${qjW) D£(S{p, a)).
Lemma 2.47. V přechodovém grafu automatu M existuje cesta
p-i A ... A pm A Qi 4 ... 4 c/n, kde m,n>1,ael, právě když qv, g %>i,a).
Jazyk přijímaný automatem .M s e-kroky definujeme
L(M) = {w e Z* | 5(qo, w)nF^ 0}.
IB102 Automaty a gramatiky, 14.10.2019
4/19
Příklad - výpočet rozšířené přechodové funkce
pro automat s e-kroky
IB102 Automaty a gramatiky, 14.10.2019
5/19
Ekvivalence automatů s e-kroky a NFA
Věta 2.48. Ke každému NFA M = (Q, 51,8, q0, F) s č-kroky existuje ekvivalentní NFA (bez č-kroků).
Důkaz. Konstrukce M = (Q, Z, 7, g0> G) bez č-kroků:
a) =     a) pro každé q g Q, a g Z
G= í F pokud D£(q0) n F = 0
\ Fu{q0} jinak
Korektnost: Dokážeme, že pro libovolné p g Q, 1/1/ g Z+ platí
(5(p51/1/) = ^(p51/1/) (indukcí vzhledem k délce slova w).
Algoritmus:
IB102 Automaty a gramatiky, 14.10.2019
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. U   =   {a1 b1'd | 2/ > j > 0}
L2   =   {a}*.{b}* L3   =   {anbn | n > 0}
/.1 n /_2 = /-s
Jazyk /_2 je regulární, L3 není regulární =4> L1 není regulární.
IB102 Automaty a gramatiky, 14.10.2019
7/19
Věta 2.52. Třída regulárních jazyků je uzavřená na zřetězení. Důkaz.
Nechť L-i a L2 jsou regulární jazyky, rozpoznávané N FA
M1 =(Q1,Z1,51,qf1,F1)aM2 = (Q2,5l2,52,Q2,/=2), kdeQi nQ2 = 0.
Definujeme N FA s e-kroky     © M2 = ^ u Q2, £1 u 5Z2,5, q^, F2), kde
5 = <$! U <?2 U {((p, e), {Q2}) I P e Fi }•
IB102 Automaty a gramatiky, 14.10.2019 8/19
Korektnost: Chceme dokázat L(M^ © M2) = L(M^).L{M2)
d: Nechť u e L{M\), tedy 3r e F| splňující r e fr\(q-\,u). Nechť v e L{M2), tedy 52(q2, v) n F2 ^ 0. Pak
č(<7i,t;v) =    |J č(p,i0 d £(r,v) d S(qz,v) = 52(q2lv).
p€$(quii)
Protože S2(q2, i/)nF2/ 0, takSfa,uv) n F2 ^ 0. Tedy ívi/ e /-(.Mi © M2).
IB102 Automaty a gramatiky, 14.10.2019
□
9/19
Věta 2.53. Třída regulárních jazyků je uzavřená na iteraci. Důkaz.
Nechť L je regulární jazyk akceptovaný NFA M = (Q, Z, 5, g0j F). Definujeme NFA s č-kroky M* = (Qu {p}, Z, 5', p, {p}), kde p^Qí
ť = í u {((p, e), {Qo})} u {((q, e), {p}) | q e F}.
IB102 Automaty a gramatiky, 14.10.2019
Uzáverové vlastnosti regulárních jazyků - Shrnutí
IB102 Automaty a gramatiky, 14.10.2019
11/19
Regulární výrazy
Definice 2.58. Množina regulárních výrazů nad abecedou Z, označovaná f?E(Z), je definována induktivně takto:
D    0 a a pro každé a e Z jsou regulární výrazy nad Z fŕzv. základní regulární výrazy).
H Jsou-li E, F regulární výrazy nad Z, jsou také (E.F), (E + F) a (E*) regulární výrazy nad Z.
B Každý regulární výraz vznikne po konečném počtu aplikací kroků 1-2.
IB102 Automaty a gramatiky, 14.10.2019
12/19
Každý regulární výraz E nad abecedou Z popisuje (jednoznačně určuje) jazyk L(E) nad abecedou Z podle těchto pravidel:
L(e)	cteŕ	{e}
L(0)	cteŕ	0
L(a)	cteŕ	{a} pro každé a e T
L( E.F)	cteŕ	L(E).L(F)
L( E + F)	def	L(E) u L(F)
L( E*)	def	L(E)*
IB102 Automaty a gramatiky, 14.10.2019
13/19
Příklady
IB102 Automaty a gramatiky, 14.10.2019
14/19
Převod regulárních výrazů na konečné automaty
RE
D FA	Věta 2.43	N FA	Věta 2.48	N FA s č-kroky
				
Věta 2.60. Nechť E je regulární výraz. Pak existuje konečný automat rozpoznávající L(E).
Důkaz. Pro libovolnou abecedu Z 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 e Z. 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, 14.10.2019
15/19
Příklad
IB102 Automaty a gramatiky, 14.10.2019
16/19
Regulární přechodový graf
Definice 2.64. Regulární přechodový graf M je pětice (Q, Z, 5, /, F),
kde
■ Q je neprázdná konečná množina stavů,
■ Z je vstupní abeceda,
■ S : Q x Q    RE(Z) je parciální přechodová funkce,
■ / c Q je množina počátečních stavů,
■ F c Q je množina koncových stavů.
IB102 Automaty a gramatiky, 14.10.2019
17/19
Příklad
IB102 Automaty a gramatiky, 14.10.2019
18/19
Slovo w g Z* je akceptováno grafem M, právě když
■ existuje posloupnost stavů q0,...,qm kde n > 0, q0 e /, qn £ F
■ a        , Q/) je definováno pro každé 0 < / < n
taková, že
■ w lze rozdělit na n částí w =   ...vn tak, že
■ Vj g L(5(q,-_i, Q,)) pro každé 0 < / < n.
Slovo e je akceptováno také tehdy, je-li / n F ^ 0.
IB102 Automaty a gramatiky, 14.10.2019
19/19