Regulární výrazy
Regulární výrazy představují další možnost popisu regulárních jazyků (právě od nich dostaly své jméno).
Definice: Množina všech regulárních výrazů nad abecedou je definována následovně:
je regulární výraz, e je regulární výraz, a je regulární výraz pro každé písmeno a∑, jsou-li r1 a r2 regulární výrazy nad abecedou
, potom r1 + r2, r1r2 a r1* jsou také regulární
výrazy nad abecedou .
Regulární výrazy
Definice: Každému regulárnímu výrazu nad abecedou odpovídá jazyk nad abecedou následovně:
regulárnímu výrazu odpovídá jazyk , regulárnímu výrazu e odpovídá jazyk {e}, regulárnímu výrazu a (a∑) odpovídá jazyk {a}, jestliže regulárnímu výrazu r1 odpovídá jazyk L1 a
regulárnímu výrazu r2 jazyk L2, potom regulárnímu výrazu r1 + r2 odpovídá jazyk L1 L2 a regulárnímu výrazu r1r2 odpovídá jazyk L1L2
a regulárnímu výrazu r1* odpovídá jazyk L1
* .
Regulární výrazy
Věta (Kleene): Jazyky definované regulárními výrazy jsou regulární jazyky, tj. jazyky rozpoznávané konečnými automaty.
Máme tři možnosti popisu každého regulárního jazyka: Regulární gramatikou Regulárním výrazem Konečným automatem
Důkaz: K regulárnímu výrazu sestavíme konečný automat (snadné) Ke konečnému automatu sestrojíme odpovídající regulární výraz
(těžší)
Regulární výrazy - cvičení
Převod regulárního výrazu na konečný automat: regulárnímu výrazu odpovídá jazyk (???), regulárnímu výrazu e odpovídá jazyk {e} (???), regulárnímu výrazu a (a∑) odpovídá jazyk {a}
(???), jestliže regulárnímu výrazu r1 odpovídá jazyk L1 a
regulárnímu výrazu r2 jazyk L2, potom regulárnímu výrazu r1 + r2 odpovídá jazyk L1 L2 (???) a regulárnímu výrazu r1r2 odpovídá jazyk L1L2
(???) a regulárnímu výrazu r1
* odpovídá jazyk L1* (???).
Regulární výrazy
Aplikace regulárních výrazů: Program grep (vyhledávání v souborech)
(Global search for Regular Expression and Print)
grep ahoj soubor grep „vystudoval \(fim\|mff\)" souborgrep -i „vystudoval \(fim\|mff\)" soubor (najde i FIM a MFF)
Využití v editorechEditor vi používá regulární výrazy k vyhledávání textu a k jeho
nahrazování. Po stisknutí stisknutím klávesy „/“ (resp. „?“ při hledání směrem vzad) napíšete regulární výraz a stisknete [Enter]. Kurzor poskočí na nejbližší následující/před chozí řetězec vyhovující zadanému výrazu.
Využití v programovacích jazycích (PERL) Využití při syntaktické analýze v překladačích
Vlastnosti regulárních jazyků
Věta: Množina slov přijatých KA s n stavy jea) neprázdná KA přijme slovo s délkou menší než n b) nekonečná KA přijme slovo s délkou d: nd<2n
Důkaz: ad a) <= platí triviálně
=> pro důkaz sporem předpokládejme, že máme nejkratší přijaté slovo a toto slovo má délku kn. Při přijímání slova délky k projde automat k+1 konfigurací a protože |Q|=n, potom při přijímání slova délky kn musí tento automat nejméně jedním stavem projít dvakrát.
Vlastnosti regulárních jazyků
Formálně lze toto zapsat: (q0,w1w2w3) …. (qx,w2w3) …. (qx,w3) …. (q,e)
Odtud je zřejmé, že také slovo w1w3 bude akceptované stejným automatem a jelikož |w1w3|<|w1w2w3|, docházíme ke sporu s předpokladem, že původní slovo bylo nejkratší.
Vlastnosti regulárních jazyků
Věta: Nechť L je regulární jazyk. Potom existuje taková konstanta p,že pro všechna slova wL & |w|p, můžeme slovo w psát ve tvaru w= w1w2w3,
kde |w2|>0, |w1w2|p a současně platí w1w2iw3L i
0.
Důkaz: K regulárnímu jazyku L existuje KA M=(Q,T,,q0,F) takový, že L = L(M). Nechť |Q|=pJestliže wL & |w|p, potom automat při přijímání tohoto slova projde automat alespoň p+1 konfigurací a protože |Q|=p, potom nutně tento automat musí nejméně jedním stavem projít dvakrát.
Vlastnosti regulárních jazyků
Formálně lze toto zapsat: (q0,w1w2w3) k (qx,w2w3) + (qx,w3) l (q,e)
Odtud je zřejmé, že také slova w1w3, w1w2w3, w1w2
2w3, … budou akceptována stejným automatem a tedy patří do L.
Význam věty
V každém „dostatečně“ dlouhém slově regulárního jazyka je obsaženo kratší neprázdné, které patří do stejného jazyka
Jeho vynecháním či naopak opakovaným přidáváním (pumpováním) dostáváme vždy slova téhož jazyka
„Pumping lemma“
Využití věty
Věta: Nechť L je regulární jazyk. Potom existuje taková konstanta p,že pro všechna slova wL & |w|p, můžeme slovo w psát ve tvaru w= w1w2w3,
kde |w2|>0, |w1w2|p a současně platí w1w2iw3L
i 0.
L regulární jazyk => platí …… w1w2iw3L i 0.
Je to implikace a tedy pokud neplatí závěr, nemůže platit ani předpoklad
Ale pozor, nelze to použít naopak (tj. pokud závěr platí, ještě to neznamená,že jazyk L je regulární)
Využití věty
Příklad: Jazyk L={0n1n|n1} je bezkontextový jazyk. a)Bezkontextový je, pokud najdeme bezkontextovou
gramatiku, která jej generuje.G=({A,S},{0,1},P,S)P={ S A | 0S1 A 01 }
b)Je regulární? Hledání gramatiky (zvlášť pokud neexistuje, bude nesmírně náročné), ale naštěstí můžeme použít předchozí větuPředpokládejme tedy, že L={0n1n|n1} je regulární jazyk.
Využití věty
Potom pro dostatečně velké n lze řetězec 0n1n zapsat jako 0n1n =w1w2w3,
přičemž w2e a w1w2iw3L i 0.
Nyní mohou nastat tři možnosti:
1.0n1n= 0k0l1n, kde k+l=n, ale 0k(0l)i1n L pro i 1
2.0n1n= 0n1k1l, kde k+l=n, ale 0n(1k)i1l L pro i 1
3.0n1n= 0k0l1r1s, kde k+l=r+s, ale 0k(0l1r)i1s L pro i 1
Tím se dostáváme do sporu s předpokladem, že jazyk L je regulární.Důsledek: L={0n1n|n1} je bezkontextový jazyk.
Trochu teorie
Příklad: Je jazyk všech slov nad abecedou {a,b}, která obsahují stejný počet znaků a a b regulární?
Důkaz: Použití věty je nyní trochu obtížnější, ale my víme, že průnik dvou regulárních jazyků je opět regulární jazykJazyk L1={w| w=a*b*} je regulární a pokud by jazyk
L2={w|w obsahuje stejný počet a a b}
byl také regulární, potom L1 L2={w| w=anbn} je také regulární,
čímž se dostáváme do sporu (jelikož víme, že regulární není)
Důsledek: L={w|w obsahuje stejný počet a a b} není regulární
Trochu teorie
Další příklady neregulárních jazyků:L1={0n1m | n>m}
L2={0n1m | n m}
L3={0n1m0n | n,m 0}
L4={ww| w{0,1}*}
L5={anbncn | n 0 } Praktický dopad:
S jazykem L={0n1n|n1} je ekvivaletní například jazyk{<begin><end>, <begin><begin><end><end>, ….}a ani tuto jednoduchou konstrukci KA neumí rozpoznat.
Regulární jazyky - shrnutí
Regulární jazyky mají mnoho užitečných vlastností, ale jejich praktické využití v oblasti programovacích jazyků a překladačů je dosti omezené (lexikální analýza)
Je nutné využít bezkontextové jazyky S nimi si již vystačíme při specifikaci většiny
konstrukcí programovacích jazyků
Bezkontextové jazyky - úvod
Překlad musí být jednoznačný (tak, jak programátor kód zamýšlel), jednoduchý a rychlý
Ne každá bezkontextová gramatika je jednoznačná, a proto nás bude zajímat možnost transformace na gramatiku s příznivějšími vlastnostmi
Budeme potřebovat opět nějaký vhodný stroj (automat), který bude slova příslušného jazyka
Bylo by užitečné, kdybychom uměli i v tomto případě najít ke konkrétní gramatice příslušný automat a naopak k danému automatu umět zapsat odpovídající gramatiku
Bezkontextové jazyky
DEF: Nechť G=(N,T,P,S) je gramatika. Potom G je gramatika typu 2 (bezkontextová), jestliže každé přepisovací pravidlo z P má tvar A , A N, (NT)*
DEF: Jazyk nazýváme bezkontextový, jestliže je možné jej generovat bezkontextovou gramatikou.
Příklad: Jazyk L={0n1n|n1} je bezkontextový jazyk. G=({A,S},{0,1},P,S)P={ S A | 0S1 A 01 } L(G) = {0n1n|n1}
Jednoznačnost gramatiky
DEF: Derivaci 0,1,2,…,n, kde každou přímou derivaci i i+1 pro 0i<k realizujeme tak, že ve větné formě i nahrazujeme první neterminál zleva (zprava) nazýváme levá (pravá) derivace.
Příklad: G=({A,S},{0,1},P,S)P={ S AB ; A 0AB |0 ; B 1 } Levá derivace:
S AB 0ABB 00BB 001B 0011Pravá derivace:
S AB A1 0AB1 0A11 0011
Jednoznačnost gramatiky
DEF: Bezkontextová gramatika G=(N,T,P,S) je nejednoznačná (víceznačná), jestliže existuje alespoň jedno slovo wL(G) takové, že pro w existuje více levých (pravých) derivací.
Příklad: G=({S},{a, b, if, then, else}, P, S)P={ S if b then S else S
S if b then S S a }
je nejednoznačná gramatika.
Jednoznačnost gramatiky
Například pro slovo if b then if b then a else a
existují následující dvě levé derivacea)S if b then S else S if b then if b then S else S
if b then if b then a else S if b then if b then a else a
b)S if b then S if b then if b then S else S if b then if b then a else S if b then if b then a else a
(Odvození začalo v prvním případě pravidlem S if b then S else S , ve druhém S if b then S )
Jednoznačnost gramatiky –problém?
a) S if b then S else S if b then if b then S else S if b then if b then a else S if b then if b then a else a
b) S if b then S if b then if b then S else S if b then if b then a else S if b then if b then a else a
a)
b)
Jednoznačnost gramatiky
Nejednoznačnost gramatiky je velký problém, protože může způsobit nejednoznačný překlad kódu
Je to problém gramatiky, nikoliv jazyka
V některých případech lze vytvořit gramatiku, která generuje stejný jazyk, ale v některých případech to nejde (vnitřně nejednoznačné gramatiky)
Otázka jednoznačnosti bezkontextových gramatik je nerozhodnutelná (neexistuje algoritmus, který by rozhodl, zda libovolná bezkontextová gramatika je či není jednoznačná)
Jednoznačnost gramatiky
Nejednoznačnost gramatiky je přesto někdy možné zjistit (například z tvaru přepisovacích pravidel) a transformovat na ekvivaletní gramatiku,která je jednoznačná.
Příklad: Nejednoznačnou gramatiku z předchozího příkladuG=({S},{a, b, if, then, else}, P, S)P={ S if b then S else S | if b then S | a } lze transformovat na G1=({S1, S2},{a, b, if, then, else}, P1, S1)
P1={S1 if b then S1 | if b then S2 else S1 | a
S2 if b then S2 else S2 | a }
a G1 je jednoznačná.
Zásobníkový automat
DEF: Zásobníkový automat M je sedmice M=(Q,,,,q0,Z0,F), kde
Q je konečná množina vnitřních stavů automatu je konečná množina vstupních symbolů (vstupní abeceda)
je konečná množina zásobníkových symbolů (zásobníková abeceda) je přechodové zobrazení : Qx({e})x Qx*q0 je počáteční stav automatu (q0Q)
Z0 je počáteční zásobníkový symbol (Z0)
F je množina koncových stavů (FQ)
Zásobníkový automat
Značení: Přechodové zobrazení: (q,a,z) (q1,z1)
znamená, že ve stavu q při čtení vstupního symbolu a a současném vyzvednutí zásobníkového symbolu z přejde zásobníkový automat (ZA) do stavu q1 a na vrch zásobníku zapíše slovo z1*
Poznámka: Zásobníkový automat může vykonat krok i bez přečtení vstupního symbolu (tj. neposune se čtecí hlava) a nemusí ani nic číst či zapisovat na zásobník. Formálně tedy uvažujeme
e= {e} a e= {e}
Zásobníkový automat
Zásobníkový automat pracuje po krocích (taktech). Činnost automatu je určena přechodovým zobrazením .
Příklad: : (q1,c,X) (q2,WX)
Poznámka: Poslední vložený symbol na zásobník se čte jako první.
a b c d e f
q1
g h
1 krok
Z
XY
a b c d e f
q2
g h
Z
XY
W
Zásobníkový automat
DEF: Nechť M=(Q,,,,q0,Z0,F) je zásobníkový automat. Potom trojici (q,w,) Qx*x * nazýváme konfigurací zásobníkového automatu M.
Konfiguraci (q0,w, Z0), kde w je vstupní řetězec nazýváme počáteční konfigurací automatu M (na zásobníku je jen Z0)
a libovolnou konfiguraci (q,e,), kde qF a *
nazýváme koncovou konfigurací automatu M (není nutné zás. vyprázdnit).
DEF: Buď M =(Q,,,,q0,Z0,F) zásobníkový automat. Potom nad množinou všech konfigurací definujeme relaci přechodu pro q1,q2Q, w *, a a * následovně:
(q1,aw,X) (q2,w,) (q2,) (q1,a,X)
Přijímání slova ZA
DEF: Nechť M=(Q,,,,q0,Z0,F) je zásobníkový automat.
Potom výpočtem ZA rozumíme posloupnost konfigurací (kroků) K0, K1, K2,…, Kn takových,že Ki Ki+1 pro i=0,..,n-1.
DEF: Nechť M=(Q,,,,q0,Z0,F) je zásobníkový automat. Potom automat M přijímá (akceptuje) slovo w *, jestliže platí (q0,w,Z0) * (q,e,) pro nějaké qF a *
Poznámka: po přečtení slova je zásobníkový automat v koncovém stavu.
DEF: Nechť M=(Q,,,,q0,Z0,F) je zásobníkový automat. Jazyk L(M) specifikovaný zásobníkovým automatem M je množina řetězců
L(M)={w| (q0,w,Z0) * (q,e, ), w *, qF, *}
Konstrukce ZA
Příklad: Navrhněte zásobníkový automat přijímající bezkontextový jazyk L={0n1n|n0}.
Řešení:Myšlenka – za každou 0 si uložíme jeden symbol na zásobník (třeba také nulu) a poté za každou jedničku jeden symbol ze zásobníku odebereme.Pokud jsme přečetli celé vstupní slovo a zásobník je prázdný, bylo na vstupu slovo z jazyka L={0n1n|n0}. Budou mi stačit čtyři stavy:q0 - počáteční stav q1 – čtu nuly a dělám si značky
q2 – čtu jedničky a mažu značky q3 – koncový stav
Konstrukce ZA
Řešení:M=({q0,q1,q2,q3},{0,1},{Z,0},,q0,Z,{q0,q3})
(q0,0,Z)= {(q1,0Z)} % začátek – čtu první nulu a dělám si
záznam
(q1,0,0)= {(q1,00)} % čtu další nuly a dělám si vždy záznam
(q1,1,0)= {(q2,e)} % čtu první 1 a mažu jednu nulu na
zásobníku
(q2,1,0)= {(q2,e)} % čtu další 1 a mažu vždy jednu nulu na
zásob.
(q2,e,Z)= {(q3,e)} % není co číst a zásobník je prázdný - stop
(q0,0011,Z) (q1,011,0Z) (q1,11,00Z) (q2,1,0Z)
(q2,e,Z) (q3,e,e)
Reprezentace stavovým diagramem
M=({q0,q1,q2,q3},{0,1},{Z,0},,q0,Z,{q0,q3})
(q0,0,Z)= {(q1,0Z)} % začátek – čtu první nulu a dělám si záznam
(q1,0,0)= {(q1,00)} % čtu další nuly a dělám si vždy záznam
(q1,1,0)= {(q2,e)} % čtu první jedničku a mažu jednu nulu na zásobníku
(q2,1,0)= {(q2,e)} % čtu další jedničku a mažu vždy jednu nulu na zásob.
(q2,e,Z)= {(q3,e)} % není co číst a zásobník je prázdný – stop
Reprezentace stavovým diagramem
Možné zjednodušení (opravdu to jde ????)
Příklady zásobníkových automatů
Příklad 1: Navrhněte zásobníkový automat přijímající bezkontextový jazyk L1={0n1m |n>m1}.
Příklad 2: Navrhněte zásobníkový automat přijímající bezkontextový jazyk L2={0n1m0n |n,m1}.
Příklad 3: Navrhněte zásobníkový automat přijímající bezkontextový jazyk L3={w3wR| w{0,1}+} (030, 131, …, 0103010, 01111311110, ….)
Příklad 4: Navrhněte zásobníkový automat přijímající bezkontextový jazyk L4={0n1m | n m}
Zásobníkový automat podruhé (a jinak)
DEF: Zásobníkový automat M je šestice M=(Q,,,,q0,Z0), kde Q je konečná množina vnitřních stavů automatu je konečná množina vstupních symbolů (vstupní abeceda)
je konečná množina zásobníkových symbolů (zásobníková
a.) je přechodové zobrazení : Qx({e})x Qx*q0 je počáteční stav automatu (q0Q)
Z0 je počáteční zásobníkový symbol (Z0)
Poznámka: Takto definovaný zásobníkový automat nemá žádné koncové stavy. Slovo je přijato, pokud se přečte celé a zásobník je prázdný.
Mluvíme o tzv. přijímání prázdným zásobníkem.
Zásobníkový automat podruhé (a jinak)
DEF: Nechť M=(Q,,,,q0,Z0) je zásobníkový automat. Potom trojici (q,w,) Qx*x * nazýváme konfigurací zásobníkového automatu M.
Konfiguraci (q0,w,Z0), kde w je vstupní řetězec nazýváme počáteční konfigurací automatu M a libovolnou konfiguraci (q,e,e), kde qQ nazýváme koncovou konfigurací automatu M.
DEF: Nechť M=(Q,,,,q0,Z0) je zásobníkový automat. Potom automat M přijímá (akceptuje) slovo w *, jestliže platí (q0,w,Z0) * (q,e,e) pro nějaké qQ.
Poznámka: po přečtení slova je zásobník prázdný.
Ekvivalence zásobníkových automatů
Věta: Nechť M1=(Q1,,1,1,q0,Z0) je zásobníkový automat přijímající prázdným zásobníkem. Potom lze sestrojit zásobníkový automat M2=(Q,,,,q0,Z0,F) přijímající koncovým stavem takový, že L(M1)=L(M2).
Myšlenka důkazu: při vyprázdnění zásobníku zařídím přechod do nově přidaného koncového stavu
Věta: Nechť M1=(Q1,,1,1,q0,Z0,F) je zásobníkový automat přijímající koncovým stavem. Potom lze sestrojit zásobníkový automat M2=(Q,,,,q0,Z0) přijímající prázdným zásobníkem takový, že L(M1)=L(M2).
Myšlenka důkazu: při dosažení koncového stavu zajistím vyprázdnění zásobníku a navíc je třeba ošetřit „předčasné-nekoncové“ vyprázdnění zásobníku
Nedeterminismus zásob. automatů
Zásobníkový automat je v principu nedeterministický (například už i tím, že jsou povoleny e-kroky, tj. změna stavu bez posunu čtecí hlavy)
Nedeterminismu lze ovšem vhodně využít i ke konstrukci automatu, který přijímá konkrétní jazyk.
Příklad: Navrhněte zásobníkový automat přijímající bezkontextový jazyk L3={wwR| w{0,1}*}
(e, 00, 11, 001100, …, 0100000010, ….)
Řešení příkladu
Myšlenka řešení: Slovo w si postupně ukládám na zásobník, ve „vhodnou“ chvíli se rozhodnu, že jsem v polovině a potom začnu porovnávat slovo wR se zápisem slova w uloženým na zásobníku.
Řešení:M=({q0,q1,q2,q3},{0,1},{Z,0,1},,q0,Z,{q0,q3})
(q0,e,Z)= {(q1,Z)} % nech si symbol Z na zásobníku
(q1,0,e)= {(q1,0)} % zapiš si nulu na zásobník
(q1,1,e)= {(q1,1)} % zapiš si jedničku na zásobník
(q1,e,e)= {(q2,e)} % jsi „možná“ uprostřed – změň stav
(q2,0,0)= {(q2,e)} % smaž si nulu ze zásobníku
(q2,1,1)= {(q2,e)} % smaž si jedničku ze zásobníku
(q2,e,Z)= {(q3,e)} % není co číst a zásob. je prázdný - stop
Reprezentace stavovým diagramem
M=({q0,q1,q2,q3},{0,1},{Z,0,1},,q0,Z,{q0,q3})
(q0,e,Z)= {(q1,Z)}
(q1,0,e)= {(q1,0)}
(q1,1,e)= {(q1,1)}
(q1,e,e)= {(q2,e)}
(q2,0,0)= {(q2,e)}
(q2,1,1)= {(q2,e)}
(q2,e,Z)= {(q3,e)}
Konstrukce automatu
Příklad: Navrhněte zásobníkový automat přijímající bezkontextový jazyk L4= {w|w obsahuje stejný počet a a b}
(e, ab, ba, aabb, abab, abba, baab, baba, bbaa, aaabbb, ….)
Myšlenka řešení: Na vstupu symbol, na zásobníku symbol Z -> ukládej na zásobník Na vstupu i na zásobníku stejný symbol -> ukládej na zásobník Na vstupu jiný symbol než na zásobníku -> maž symbol ze
zásobníku
