r
Věta 2.60
DFA	Věta 2.43	NFA	Věta 2.48 j
	s		\
v_ _J			
NFA s £-kroky
Kleeneho veta 2.63. Libovolný jazyk jě popsatělny regulárním vyrazěm pravě kdyZ jě rozpoznatelný koněcnym automatem.
IB102 Automaty a gramatiky, 25.10.2010
1
Regulární přechodový graf
Definice 2.64.
Regulární přechodový graf M je petice (Q, E, 5,I, F), kde
• Q je neprázdná koneCná množina stavů.
• E je vstupní abeceda.
• 5 : Q x Q — RE(E) je parcialn í prechodova fůnkce.
• I ^ Q je množina pocatecn ích stavů.
• F C Q je množina koncových stavů.
IB102 Aůtomatý a gramatiky, 25.10.2010
2
Příklad
IB102 Automaty a gramatiky, 25.10.2010
3
Slovo w G S* je grafem M akceptováno, právě když
• existuje posloupnost stavů q0,..., qn, kde n > 0, q0 G I, qn G F
• a 5(qi_i,qi) je definováno pro každe 0 < i < n
taková, že
• w lže roždelit na n častí w = v1... vn tak, že
• Vi G L(5(qi_1,qi)) pro každe 0 < i < n.
Slovo e je akceptovano take tehdy, je-li I n F = 0.
IB102 Automaty a gramatiky, 25.10.2010
4
Převod regulárního přechodového grafu na NFA
Motivace
Véta  2.65. Pro libovolný regulární přechodový graf M =
(Q, S, ô, I, F) existuje ekvivalentní NFA MM s £-kroký.
IB102 Automaty a gramatiky, 25.10. 2010 5
Důkaz. Algoritmus konstrukce NFA M s £-kroky.
IB102 Automaty a gramatiky, 25. 10. 2010
6
Krok 1 Ke grafu M přidáme nový stav qo a hranu qo — q pro každé q G I. Stav qo bude (jediným) počatečním stavem automatu M*, prvký F jeho koncovými stavý.
IB102 Automatý a gramatiký, 25.10.2010
7
Krok 2 Opakovaně realizuj kroky (a) a (b) dokud přechodový graf obsahuje alespoř jednu hranu ohodnocenou symbolem, který nepatří do S U [e], tedy je tvaru F + G, F.G, F * nebo 0.
(a) Odstrař všechny hrany, ktere jsou ohodnoceny symbolem 0.
(b) Vyber libovolnou hranu p — q, kde E 0 S U [e], odstrař ji a proveci nasledující:
IB102 Automaty a gramatiky, 25.10.2010
8
KoneCnost algoritmu M obsahuje pouze koneCne mnoho hran, tj. koneCne mnoho regularn ích výrazu. KaZdý regularn í výraz obsahuje jen koneCne mnoho výskýtu +, . a *. V kaZdem kroku 2(b) jeden výskýt odstran íme.
Korektnost algoritmu
• Výsledný graf je přechodovým grafem nedeterministickeho koneCneho automatu M s £-kroký.
• Prímo z definice regularn ího přechodoveho grafu se snadno overí, Ze kroký 1 a 2 popsaneho transformacn ího algoritmu zachovavaj í ekvivalenci automatu, proto L(M) = L(M').
□
IB102 Automatý a gramatiký, 25.10.2010
9
Prevod DFA na reguiarní prechodový graf
Motivace
Veta   2.66. Pro   kaZdy   regularn í  prechodovy  graf  M =
(Q, S,ô,I,F) existuje ekvivalentn í regularn í prechodovy graf M' = ({x, y}, S, ô', {x}, {y}), kde ô' rrmZe byt definovano pouze pro dvojici
IB102 Automaty a gramatiky, 25. 10. 2010 10
Důkaz. Algoritmus transformace
Krok 1 Ke grafu M pridáme nový poCateCní stav x a nový koncový stav y. Pridame take hraný x q pro každe q G I a r y pro každe r G F.
IB102 Automaty a gramatiky, 25.10.2010
11
Krok 2 Každý stav p různý od x,y nyn í odstraň íme spolu s hranami, které do p vchazej í nebo z p vychazej í. Pokud do p nevede hrana z jineho uzlu, je nedosazitelný z poCateCn ího stavu. Pokud z p nevede hrana do jineho uzlu, nelze z p dosahnout koncový stav. V obou případech p odstran íme bez nahrady.
Pro kazdou dvojici vstupn í hrany vedouc í do p z jineho uzlu a výstupn í hrany vedouc í z p do jineho uzlu přidame prímý prechod. Pak p odstran íme.
_\
>
7
E
_\
>
7
IB102 Automaty a gramatiky, 25.10.2010
12
ri
E
íF2
'i
i1
G2X7
->
Fi.(E+0)*.Gi
//^.(E+0)*.Gi
\ Fi.(E+0)*.G2
F2.(E+0)*.G2
Po odstraněn í vsech stavů různých od x a y zůstanou tyto dva stavy spolu s (zadnou nebo jednou) hranou z x do y.
Konečnost algoritmu    Kazdým krokem 2 sn íz íme poCet stavu.
Korektnost algoritmu Z definice reguiarn ího prechodoveho grafu prímo overíme, ze kroky 1 i 2 zachovavaj í ekvivalenci. □
IB102 Automaty a gramatiky, 25.10.2010
13
Ekvivalence konečných automatů a regulárních gramatik
Pojem regulárního jazyka byl definován dvakrát - nejprve pomocí regulární gramatiky a pak jeste jednou pomocí koneCneho automatu.
IB102 Automaty a gramatiky, 25.10.2010
14
Prevod regulární gramatiky na konečný automat
Lemma 2.69. Ke každe regularní gramatice G = (N, S, P, S) existuje nedeterministický konečný automat M = (Q, S,ô,qo, F) takový, že L(G) = L(M).
DUkaz.
IB102 Automatý a gramatiký, 25. 10. 2010
15
Konstrukce koneCneho automatu
• Q = {A | A G N} U {g/}, kde qf 0 N.
• <7o = S.
• 5 je nejmens í fůnkce Q x E — 2Q splňůj íc í:
- Pokud A —> a£> je pravidlo v P, pak B G a).
- Pokud A —» a je pravidlo v P, kde a ^ e, pak gj G a)
í {£, g/}   pokud 5 —» e je pravidlo v P,
{qf}
jinak.
IB102 Aůtomatý a gramatiký, 25. 10. 2010
16
Korektnost Nejprve indukcí vzhledem ke k dokážeme, že pro každé ai,..., afc G £ a B G N platí
S      ai... akB   <   >   B G 5(S, ai... ak).
• Základní krok k = 0:     Z definice <5 plyne 5(5, č:) = {5}. Proto
5^*B    ^    5 = 5    ^    B = Š   ^ Bg5(5>)
• Indukční krok:
S      ai... afc+iB
3C G N takove, že S =^>* ai... akC =>* ai... ak+iB <^=> 3C g N takové, že C g 5(5, ai... ak) A C —> ak+1B <=> 3C g TV takové, že C g 5(5, ai... afc) A ~B g 5(C, afc+i) <^=^ B G 5(S, ai... afc+i)-
IB102 Automaty a gramatiky, 25.10.2010
17
Dokazali jsme:     S =^>* a1... akB Ukazeme, ze w G L(G)       w G L(M):
£> g (5(5, dl . . . ttfe)
• w = e:
e g ^ S^íGP ^ Š g F ^ e g
• w = va, kde v G S*, a G S:
va G L(G) S =>* vB => va
S ^* vB A B     a G P
<=>   Beô(Š,v) A qfeö(B,a) <=>   qfe5(S,va) va e L(M)
□
IB102 Automaty a gramatiky, 25.10.2010
18
Prevod koneCneho automatu na regulárni gramatiku
Lemma 2.71 Pro každy konečný automat M = (Q, S,5,q0, F) existuje regularní gramatika G = (N, S, P, S) takova, že L (M) = L(G).
Dukaz.
IB102 Automaty a gramatiky, 25. 10. 2010
19
Bez ujmý na obecnosti předpokladejme, ze M je nedeterministický.
• N = {q I q G Q} U {S}, kde S 0 Q.
• P je nejmens í mnozina pravidel splřuj íc í:
- Pokud p G      a), je q —» ap pravidlo v P.
- Pokud p G      a) a p G F, je g —» a pravidlo v P.
- Pokud p G 5(<?o? a)» Je ^ —> ap pravidlo v P.
- Pokud p G ô(q0, a) a p G F, je S — a pravidlo v P.
- Pokud qo G F, je S — e pravidlo v P.
Gramatika G = (N, S, P, S) je zřejme regularn í.
/\
Plat í:   S(qo, ai... ak) n F = 0, kde k > 0,ai,...,ak G S
<^=^ S      ai... ak
IB102 Automatý a gramatiký, 25. 10. 2010
20
Rozhodnutelne probiemy pro trídu reg. jazykU
Regularní jažýk - popsaný nekterým ž uvažovaných formalismu. Otazky: Mame-li daný konecne automatý M a M* nad S
ekvivalence: jsou M a M* ekvivalentn í? (plat í L(M)=L(M*) ?) inkluze (jažýku): plat í L (M) C L (M*) ?
príslušnost (slova k jažýku): je-li dano w G S*, plat í w G L (M) ? prazdnost (jažýka): je L (M) = 0 ? univerzalita (jažýka): je L( M) = S* ? konečnost (jažýka): je L(G) konecný jažýk?
IB102 Automatý a gramatiký, 25. 10. 2010
21
Věta 2.74 Problém prázdnosti (L(M) = 0) a problém univerzality (L(M) = S*) jsou rozhodnutelné pro régularn í jazyky.
DUkaz. L(M) jé prázdny, pravé kdyZ mézi dosaZitélnymi stavy automatu M nén ízadny koncovy stav.
Univérzalita: L(M) = S* co-L(M) = 0. □
Veta 2.77 Problem ekvivalence je rozhodnutelny pro reguiarn í jazyky. DUkaz. Pro libovolne Li,L2 plat í:
(Li = L2) (Li n co-L2) U (co-Li n L2) = 0.
Pro Li? L2 zadane automaty lze uvedene operace algoritmicky realizovat. Alternativně: minimalizace a kanonizace. □
IB102 Automaty a gramatiky, 25. 10. 2010 22
Veta 2.76 Problem, žda jažyk L žadany automatem M je koneCný, resp. nekoneCný, je rožhodnutelny.
Diikaz. Necht M je DFA. L je nekonečny prave když M akceptuje alespon jedno slovo w G S* s vlastností n < |w| < 2n, kde n = card(Q).
(=^) L nekonečny, pak existuje u G L takove, že |u| > n. Je-li |u| < 2n, jsme hotovi.
Necht |u| > 2n. Z lemma o vkladaní plyne, že u = xyz, kde 1 < |y| < n a xz G L. Platí |xz| > n. Pokud |xz| > 2n, cely postup opakujeme.
(<^=) |w| > n, pak M na w musí projít dvakrat stejnym stavem. Proto w = xyz tak, že |y| > 1 a platí xyiz G L pro každe i G N0 (viž dukaž lemmatu o vkladaní), tedy L je nekonecny.
Existenci w G L takoveho, že n < |w| < 2n, lže algoritmicky overit (slov je konecne mnoho/vyžkoušíme'' každe ž nich). □
IB102 Automaty a gramatiky, 25. 10. 2010
23
Aplikace reg. jazyků a konečných automatů
vyhledáván í vzorů (pattern matching) v textu (editory, textové systémy), DNA sekvenc ích, . . . Napríklad v Unixu:
grep - vyhledáván í podle zadaneho regularn ího vyrazu
egrep - vyhledavan í podle zadaneho rozs íreneho regularn ího vyrazu
fgrep - vyhledavan í podle zadaneho retezce
Zpracovan í lexikaln ích jednotek napríklad pri automatizovane konstrukci prekladaču (lex, flex)
Zpracovan í obrazů (image processing)
Konecne automaty nad nekonecnymi slovy
Specifikace a verifikace konecne stavovych systemu
Konecne automaty s vystupem
IB102 Automaty a gramatiky, 25.10.2010
24