Prevod regulárního přechodového grafu na NFA
Motivace
Veta 2.65. Pro libovolný regulární přechodový graf M = (Q, Z, 5, /, F) existuje ekvivalentní NFA M! s č-kroky.
IB102 Automaty a gramatiky, 22.10.2018 1/21
Důkaz. Algoritmus konstrukce N FA M' s č-kroky.
IB102 Automaty a gramatiky, 22.10.2018
2/21
Krok 1: Ke grafu M přidáme nový stav q0 a hranu q0 A q pro každé q g /. Stav g0 bude (jediným) počátečním stavem automatu M', prvky F jeho koncovými stavy.
IB102 Automaty a gramatiky, 22.10.2018
3/21
Krok 2: Opakovaně realizuj kroky (a) a (b) dokud přechodový graf obsahuje alespoň jednu hranu ohodnocenou symbolem, který nepatří do Z u {e}, tedy je tvaru F + G, F. G, F* nebo 0.
(a) Odstraň všechny hrany, které jsou ohodnoceny symbolem 0.
(b) Vyber libovolnou hranu p -> q, kde E ^ Z u {s}, odstraň ji a proveď následující:
IB102 Automaty a gramatiky, 22.10.2018
4/21
Konečnost algoritmu M obsahuje pouze konečně mnoho hran, tj. konečně mnoho regulárních výrazů. Každý regulární výraz obsahuje jen konečně mnoho výskytů +, . a *. V každém kroku 2(b) jeden výskyt odstraníme.
Korektnost algoritmu
■ Výsledný graf je přechodovým grafem nedeterministického konečného automatu M! s č-kroky.
■ Přímo z definice regulárního přechodového grafu se snadno ověří, že kroky 1 a 2 popsaného transformačního algoritmu zachovávají ekvivalenci automatů, proto L(M) = L(M'). □
IB102 Automaty a gramatiky, 22.10.2018
5/21
Převod DFA na regulární výraz
Motivace
Věta 2.66. Pro každý regulární přechodový graf M = (Q, 51, S, /, F) existuje ekvivalentní přechodový graf M' = ({x, y}, Z, 5', {x}, {y}), kde (5; může být definováno pouze pro dvojici (x,y).
IB102 Automaty a gramatiky, 22.10.2018 6/21
Důkaz. Algoritmus transformace
Krok 1: Ke grafu M přidáme nový počáteční stav x a nový koncový stav y. Přidáme také hrany x A q pro každé q e I a r A y pro každé r e F.
IB102 Automaty a gramatiky, 22.10.2018
7/21
Krok 2: Každý stav p různý od x, y nyní odstraníme spolu s hranami, které do p vcházejí nebo z p vycházejí.
Pokud do p nevede hrana z jiného uzlu, je nedosažitelný z počátečního stavu. Pokud z p nevede hrana do jiného uzlu, nelze z p dosáhnout koncový stav. V obou případech p odstraníme bez náhrady.
Pro každou dvojici vstupní hrany vedoucí do p z jiného uzlu a výstupní hrany vedoucí z p do jiného uzlu přidáme přímý přechod. Pak p odstraníme.
IB102 Automaty a gramatiky, 22.10.2018
8/21
Po odstranění všech stavů různých od x a y zůstanou tyto dva stavy spolu s (žádnou nebo jednou) hranou z x do y.
Konečnost algoritmu Každým krokem 2 snížíme počet stavů.
Korektnost algoritmu Z definice regulárního přechodového grafu přímo ověříme, že kroky 1 i 2 zachovávají ekvivalenci. □
Na regulární výraz lze stejně převést každý konečný automat (nejen DFA).
IB102 Automaty a gramatiky, 22.10.2018 9/21
Ekvivalence konečných automatů a reg. výrazů
RE
D FA	Věta 2.43	N FA	Věta 2.48	N FA s č-kroky
				
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, 22.10.2018
10/21
Ekvivalence konečných automatů a regulárních gramatik
Věta 2.60, Věta 2.65
r
RE	Věta 2.66	D FA	Věta 2.43	N FA
				
				
Věta 2.48
N FA s č-kroky
Reg. gramatiky
Pojem regulárního jazyka byl definován dvakrát - nejprve pomocí regulární gramatiky a pak ještě jednou pomocí konečného automatu.
IB102 Automaty a gramatiky, 22.10.2018
11/21
Převod regulární gramatiky na konečný automat
Lemma 2.69. Ke každé regulární gramatice Q = (A/, Z, P, S) existuje nedeterministický konečný automat M = (Q, Z, 5, Qo> O takový, že L(É0 = Z.(A<).
Důkaz.
IB102 Automaty a gramatiky, 22.10.2018
12/21
Konstrukce konečného automatu M = (Q, Z, 5, g0> ^)
■ Q = {Ä \ Ae N}u {qf}, kde qf ^ N
■ Qo =Š
■ 5 je nejmenší funkce Q x I    2° splňující:
- pokud A    aB je pravidlo v P, pak S g 5(A a)
- pokud >A    a je pravidlo v P, kde a ^   pak qy e 5(A a)
{S, qy} pokud S s je pravidlo v P {Qf} jinak
IB102 Automaty a gramatiky, 22.10.2018
13/21
Korektnost Nejprve indukcí vzhledem ke k dokážeme, že pro každé a\,..., ak g Z a B g N platí:
S =*►* ai... akB  ^>   B e S(Š, a^... ak)
■ Základní krok k = 0: Z definice 8 plyne 8{Š, e) = {Š} a proto:
S^*6 B=S B = S   <^ BGč(Š,e)
■ Indukční krok:
S =>* a-\... 3/c+i B
<^=> 3C e N takové, že S     ai... akC ^ a^... ak+A B 3Ce N takové, že Č g <5(Š, a^...ak) a C ->• a/<+1 B 3C e N takové, že C e S(Š7 ai...ak) a B g      afc+1) 6 g <5(S, a-i... a/(_|_i).
IB102 Automaty a gramatiky, 22.10.2018
Dokázali jsme:   S^*a^...akB   ^>   B g 5(S,a^ ... ak)
Ukážeme, že w g L(Q) <=^> w g L(M)\ m w = e:
s g L{Q) S^eeP        Š e F e g /_(M)
■ 1/1/ = va, kde i/Gr,aGl:
va g L(G) S^* vB^ va
S=>*vBAB^>aeP Š g ô(Š, v) a qf e ô(B, a) <=^>   qf g <5(S, va)   <==^>   va g /-(.A/í)
IB102 Automaty a gramatiky, 22.10.2018
Převod konečného automatu na regulární gramatiku
Lemma 2.71 Pro každý konečný automat M = (Q, 51, S, g0, F) existuje regulární gramatika g = (N, E, P, S) taková, že L(M) = L(Q).
Důkaz.
IB102 Automaty a gramatiky, 22.10.2018
16/21
Bez újmy na obecnosti předpokládejme, že M je nedeterministický.
■ N = {q I q g Q} u {S}, kde S ^ Q.
m P je nejmenší množina pravidel splňující:
- pokud p g      a), je q    ap pravidlo v P
- pokud p g 5(q, a) a p g F, je q    a pravidlo v P
- pokud p g (5(c7o, a), je S    ap pravidlo v P
- pokud p g 5(qo, a) a p g F, je S    a pravidlo v P
- pokud q0 e F,\e S ^ e pravidlo v P
Gramatika Q = (A/, Z, P, S) je zřejmě regulární.
Platí: S(q0, a-i ... a^) n F 7^ 0, kde /c > 0, a-i,...,    e Z
<^=>* S     a-j ... a/e
IB102 Automaty a gramatiky, 22.10.2018
Rozhodnutelné problémy pro třídu reg. jazyků
Regulární jazyk - popsaný některým z uvažovaných formalismů.
Otázky: Máme-li dány konečné automaty MaM' nad Z
■ ekvivalence: jsou MaM' ekvivalentní? (platí L(M)=L(Mf) ?)
■ inkluze (jazyků): platí L(M) c L(M')?
■ příslušnost (slova k jazyku): je-li dáno w e Z*, platí w e L(M)?
■ prázdnost (jazyka): je L(M) = 0?
■ univerzalita (jazyka): je L(M) = Z*?
■ konečnost (jazyka): je L(M) konečný jazyk?
IB102 Automaty a gramatiky, 22.10.2018
18/21
Věta 2.74 Problém prázdnosti (L(M) = 0) a problém univerzality
(L(M) = 51*) jsou rozhodnutelné pro regulární jazyky.
Důkaz. L(M) je prázdný, právě když mezi dosažitelnými stavy automatu M není žádný koncový stav.
Univerzalita: L(M) = Z* ^ co-L(M) = 0. □
Věta 2.77 Problém ekvivalence je rozhodnutelný pro regulární jazyky.
Důkaz. Pro libovolné Li, L2 platí:
=l2) ^> (/-i n co-L2) u {co-Li n L2) = 0.
Pro L-i, L2 zadané automaty lze uvedené operace algoritmicky realizovat. Alternativně: minimalizace a kanonizace. □
IB102 Automaty a gramatiky, 22.10.2018
19/21
Věta 2.76 Problém, zda jazyk L zadaný automatem M je konečný, resp. nekonečný, je rozhodnutelný.
Důkaz. Nechť M je DFA. L je nekonečný právě když M akceptuje alespoň jedno slovo ^Gľs vlastností n < \ w\ < 2n, kde n = card(Q).
(=4>) Je-li L nekonečný, pak existuje u e L takové, že \u\ > n. Je-li \u\ < 2n, jsme hotovi. Nechť \u\ > 2n. Z lemma o vkládání plyne, že u = xyz, kde 1 < \y\ < n a xz e L. Platí \xz\ > n. Pokud \xz\ > 2n, celý postup opakujeme.
(<==) Je-li \ w\ > n, pak M při čtení w musí projít dvakrát stejným stavem. Proto w = xyz tak, že \y\ > 1 a platí xy'z e L pro každé / g n0 (viz důkaz lemmatu o vkládání), tedy L je nekonečný.
Existenci w e /-takového, že n < \ w\ < 2n, lze algoritmicky ověřit (slovje konečně mnoho,„vyzkoušíme" každé z nich). □
IB102 Automaty a gramatiky, 22.10.2018
20/21
Aplikace reg. jazyků a konečných automatů
■ Vyhledávání vzorů (pattern matching) v textu (editory, textové systémy), DNA sekvencích, ...
Například v Unixu:
grep - vyhledávání podle zadaného regulárního výrazu
egrep - vyhledávání podle zadaného rozšířeného regulárního výrazu
f grep - vyhledávání podle zadaného řetězce
■ Zpracování lexikálních jednotek například při automatizované konstrukci překladačů (lex, f lex)
■ Zpracování obrazů (image processing)
■ Konečné automaty nad nekonečnými slovy
■ Specifikace a verifikace konečně stavových systémů
■ Konečné automaty s výstupem
IB102 Automaty a gramatiky, 22.10.2018
21/21