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, gramatiky a složitost, 10.10.2016
1/29
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, gramatiky a složitost, 10.10.2016
2/29
Příklady
IB102 Automaty, gramatiky a složitost, 10.10.2016
3/29
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, gramatiky a složitost, 10.10.2016
4/29
Příklad
IB102 Automaty, gramatiky a složitost, 10.10.2016
5/29
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, gramatiky a složitost, 10.10.2016
6/29
Příklad
IB102 Automaty, gramatiky a složitost, 10.10.2016
7/29
Slovo w g Z* je akceptováno grafem M, právě když
■ existuje posloupnost stavů q0,...,qm kde n > 0, q0 g /, qn g 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, gramatiky a složitost, 10.10.2016
8/29
Prevod regulárního prechodového grafu na NFA
Motivace
Věta 2.65. Pro libovolný regulární přechodový graf M = (Q, Z, 5, /, F) existuje ekvivalentní NFA M' s č-kroky.
IB102 Automaty, gramatiky a složitost, 10.10.2016 9/29
Důkaz. Algoritmus konstrukce N FA M' s č-kroky.
IB102 Automaty, gramatiky a složitost, 10.10.2016
10/29
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, gramatiky a složitost, 10.10.2016
11/29
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, gramatiky a složitost, 10.10.2016
12/29
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, gramatiky a složitost, 10.10.2016
13/29
Převod DFA na regulární výraz
Motivace
Věta 2.66. Pro každý regulární přechodový graf M = (Q, Z, 5, /, F) existuje ekvivalentní přechodový graf M! = ({x, y}, Z, {x}, {y})5 kde (5; může být definováno pouze pro dvojici (x,y).
IB102 Automaty, gramatiky a složitost, 10.10.2016 14/29
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, gramatiky a složitost, 10.10.2016
15/29
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, gramatiky a složitost, 10.10.2016
16/29
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, gramatiky a složitost, 10.10.2016 17/29
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, gramatiky a složitost, 10.10.2016
18/29
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, gramatiky a složitost, 10.10.2016
1
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, g0j O takový, že L{G) = L(M).
Důkaz.
IB102 Automaty, gramatiky a složitost, 10.10.2016
20/29
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, gramatiky a složitost, 10.10.2016
21/29
Korektnost Nejprve indukcí vzhledem ke k dokážeme, že pro každé ai,...,ak eZaB e N platí:
S=>*ai...akB Be$(Š,ai...ak)
■ Základní krok k = 0: Z definice ô plyne S(Š, e) = {Š} a proto:
S^*S B=S    <=ť    B = Š    ^ Be5(Š,e)
■ Indukční krok:
S     a-| ... B
•<=>• 3C e N takové, že S =>* a-i ... akC =>• ai... ak+\ B 3C e N takové, že Č g Sis, a^...ak) a C -» ak+i B 3Ce N takové, že Č € ô(Š, a^...ak) a Bg 6(Č, ak^) B e ó(S,a-\... ak+-\).
IB102 Automaty, gramatiky a složitost, 10.10.2016
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, gramatiky a složitost, 10.10.2016
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, gramatiky a složitost, 10.10.2016
24/29
Bez újmy na obecnosti předpokládejme, že M je nedeterministický.
■ N = {q I q g Q} u {S}, kde S 0 Q.
■ P je nejmenší množina pravidel splňující:
- pokud p g 5(q, a), je q    äp pravidlo v P
- pokud p g      a) a p g F, je q    a pravidlo v P
- pokud p g 5(qo, a), je S    äp pravidlo v P
- pokud p g (5(c7o, ^) a p g F, je S    a pravidlo v P
- pokud Qo e F, je S    £ pravidlo v P
Gramatika £ = (A/, Z, P, S) je zrejme regulárni.
Platí: S(q0, a-i ... a^) n F 7^ 0, kde /c > 0, a-i,...,    e Z
<^=>* S     a-j ... a/e
IB102 Automaty, gramatiky a složitost, 10.10.2016
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, gramatiky a složitost, 10.10.2016
26/29
Věta 2.74 Problém prázdnosti (L(M) = 0) a problém univerzality
(L(M) = Z*) 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, gramatiky a složitost, 10.10.2016
27/29
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, gramatiky a složitost, 10.10.2016
28/29
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, gramatiky a složitost, 10.10.2016
29/29