Regulární výrazy
Definice 2.58. Množina regulárních výrazů nad abecedou Z, označovaná flE(Z), je definována induktivně takto:
D    0 a a pro každé a e Z jsou regulární výrazy nad Z (tzv. 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, 6.10.2014
1/29
Každý regulární výraz E nad abecedou Z popisuje (jednoznačně určuje) jazyk Z_(E) nad abecedou Z podle těchto pravidel:
L(e)	def	{e}
L(0)	def	0
L(a)	def	{a} pro každé a e T
L( E.F)	def	L(E).L(F)
L(E+F)	def	L(E) u L(F)
L( E*)	def	L(EY
IB102 Automaty, gramatiky a složitost, 6.10.2014
2/29
Příklady
IB102 Automaty, gramatiky a složitost, 6.10.2014
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, 6.10.2014
4/29
Příklad
IB102 Automaty, gramatiky a složitost, 6.10.2014
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,
■ 5 : Q x Q    RE(H) 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, 6.10.2014
6/29
Příklad
IB102 Automaty, gramatiky a složitost, 6.10.2014
7/29
Slovo w g Z* je akceptováno grafem M, právě když
■ existuje posloupnost stavů q0,...,qn, 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(g/_i, Q,)) pro každé 0 < i < n.
Slovo e je akceptováno také tehdy, je-li / n F ^ 0.
IB102 Automaty, gramatiky a složitost, 6.10.2014
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, 51, S, /, F) existuje ekvivalentní NFA M' s č-kroky.
IB102 Automaty, gramatiky a složitost, 6.10.2014 9/29
Důkaz. Algoritmus konstrukce N FA M' s č-kroky.
IB102 Automaty, gramatiky a složitost, 6.10.2014
10/29
Krok 1: Ke grafu M přidáme nový stav q0 a hranu q0 A q pro každé q g /. Stav Qo bude (jediným) počátečním stavem automatu M', prvky F jeho koncovými stavy.
IB102 Automaty, gramatiky a složitost, 6.10.2014
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, 6.10.2014
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, 6.10.2014
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, 51, S, /, F) existuje ekvivalentní přechodový graf M' = ({x, y}, Z, í7, {x}, {y}), kde č' může být definováno pouze pro dvojici (x,y).
IB102 Automaty, gramatiky a složitost, 6.10.2014 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 g F.
IB102 Automaty, gramatiky a složitost, 6.10.2014
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, 6.10.2014
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, 6.10.2014 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, 6.10.2014
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.62	D FA	Věta 2.43	N FA
	Věta 2.66			
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, 6.10.2014
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, g0> O takový, že L{G) = L(M).
Důkaz.
IB102 Automaty, gramatiky a složitost, 6.10.2014
20/29
Konstrukce konečného automatu M = (Q, 51, S, q0l F) m Q = (Ä \ Ae N}u {qf}, kde qf N ■ Qo =Š
m S je nejmenší funkce Q x I    2° splňující:
- pokud A    afí je pravidlo v P, pak   g č(/4, a)
- pokud A    a je pravidlo v P, kde a^e, pak qf e 5(A, ä)
{S, qf} pokud S e je pravidlo v P {Qf} jinak
IB102 Automaty, gramatiky a složitost, 6.10.2014
21/29
Korektnost Nejprve indukcí vzhledem ke k dokážeme, že pro každé at\,..., ak e 51 a B e N platí:
S=>* a^... akB B e S(Š, a^... ak)
■ Základní krok k = 0: Z definice 6 plyne $(Š, s) = {Š} a proto:
S=>*B   ^    B=S B = Š Be$(Š,e)
■ Indukční krok:
S =4>* a-i ... B
<^> 3C e N takové, že S     a-i... akC a-\... ak+i B
3C e N takové, že Č e S(Š, a-\ ...ak) A C -> a^+i B
3C e N takové, že Č e 5(Š, ^ ... ak) A Bg í(Č, a^+i) S e <5(S, a-i... a/c+i).
IB102 Automaty, gramatiky a složitost, 6.10.2014
Dokázali jsme:    S^*a^...akB   ^>   B e 5(S,a^ ... ak)
Ukážeme, že w g L(Q) <=^> w g L{M)\ m w = s:
s g L(Q) S^eeP        Š g F ^ g L(.M)
■ w = va, kde v g Z*, a g Z:
va g L(G) S^* vB^ va
S=>*vBAB->aeP fí g 5(Š, v) A    g 5(8, a) <=4>   Q/ g <5(S, va)   <=^>   va g /-(.M)
IB102 Automaty, gramatiky a složitost, 6.10.2014
Převod konečného automatu na regulární gramatiku
Lemma 2.71 Pro každý konečný automat M = (Q, I, S, g0, F) existuje regulární gramatika Q = (N, E, P, S) taková, že L(M) = L(G).
Důkaz.
IB102 Automaty, gramatiky a složitost, 6.10.2014
24/29
Bez újmy na obecnosti předpokládejme, že M je nedeterministický.
■ N = {q I q g Q} u {S}, kde S £ Q.
■ P je nejmenší množina pravidel splňující:
- pokud p g      a), je q    äp pravidlo v P
- pokud p g 5(q, a) a p g F, je q    a pravidlo v P
- pokud p g (5(q0, a), je S    ap pravidlo v P
- pokud p g 5(qo, a) a p g F, je S    a pravidlo v P
- pokud Qo e F, je S    e pravidlo v P
Gramatika Q = (A/, Z, P, S) je zřejmě regulární.
Platí: 5(qo, a-i ... a^) n F 7^ 0, kde /c > 0, ai,..., a^ g Z
<^=>* S     a-j ... a^
IB102 Automaty, gramatiky a složitost, 6.10.2014
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 M a M! nad Z
■ ekvivalence: jsou M a M' ekvivalentní? (platí L(M)=L(M') ?)
■ inkluze (jazyků): platí L(M) c L(M')7
■ příslušnost (slova k jazyku): je-li dáno w e Z*5 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, 6.10.2014
26/29
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é L|, l2 platí:
=l2) ^> (/-i n co-l2) u (co-Z-i n l2) = 0.
Pro /.-i, l2 zadané automaty lze uvedené operace algoritmicky realizovat. Alternativně: minimalizace a kanonizace. □
IB102 Automaty, gramatiky a složitost, 6.10.2014
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. /.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í xylz e L pro každé / g N0 (viz důkaz lemmatu o vkládání), tedy Z. 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, 6.10.2014
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, 6.10.2014
29/29