Lexikálna analýza. Regulárne jazyky a konečné automaty
celkovým počtom znakov abecedy symbolov a prevádzkových znakov a zátvoriek v hesle r.Základ. Automaty pre výrazy dĺžky 1: a sú zobrazené na nasledujúcom obrázku.
Ryža. 5.1.
Všimnite si, že pre každý z týchto troch automatov množina konečných stavov pozostáva z jedného stavu.
Indukčný krok. Teraz predpokladajme, že pre každý regulárny výraz dĺžky = 1 možno slovo w rozdeliť na k podslov: w=w 1 w 2 ... w k a je to. Pre každé i= 1,... ,k slovo w i prekladá q 0 1 na q f 1 . Potom pre slovo w v diagrame M existuje cesta
Preto, . Naopak, ak nejaké slovo preloží q 0 na q f , potom buď existuje, alebo je vedené cestou, ktorá prejde z q 0 do q 0 1 a potom niekoľkokrát prejde po ceste z q 0 1 do q f 1 a vráti sa späť z q f 1 na q 0 1 -prechodom, nakoniec z q f 1 -prechodom končí na q f . Preto také slovo.
Z viet 4.2 a 5.1 priamo získame
Dôsledok 5.1. Pre každý regulárny výraz je možné efektívne zostaviť deterministický konečný automat, ktorý rozpoznáva jazyk reprezentovaný týmto výrazom.
Toto tvrdenie je jedným z príkladov teorémov o syntéze: na základe popisu úlohy (jazyk ako regulárny výraz) je efektívne skonštruovaný program (DFA), ktorý ju vykonáva. Platí to aj naopak - teorém analýzy.
Veta 5.2. Pre každý deterministický (alebo nedeterministický) konečný automat je možné skonštruovať regulárny výraz, ktorý predstavuje jazyk rozpoznaný týmto automatom.
Dôkaz tejto vety je dosť technický a presahuje rámec nášho kurzu.
Môžeme teda konštatovať, že trieda jazykov konečných automatov sa zhoduje s triedou regulárnych jazykov. Odteraz to budeme nazývať jednoducho triedou jazykov automatov.
Automat M r, ktorý je skonštruovaný v dôkaze vety 5.1
Základné definície Regulárne výrazy v abecede Σ a regulárne množiny, ktoré označujú, sú definované rekurzívne takto: 1) – regulárny výraz označujúci regulárnu množinu; 2) e – regulárny výraz označujúci regulárnu množinu (e); 3) ak a Σ, potom a je regulárny výraz označujúci regulárnu množinu (a); 4) ak p a q sú regulárne výrazy označujúce regulárne množiny P a Q, potom a) (p+q) je regulárny výraz označujúci P Q; b) pq – regulárny výraz označujúci PQ; c) p* – regulárny výraz označujúci P*; 5) nič iné nie je regulárny výraz.
Základné definície Prioritizácia: * (iterácia) – najvyššia priorita; zreťazenie; + (únia). Takže 0 + 10* = (0 + (1 (0*))). Príklady: 1.01 znamená (01); 2. 0* – (0*); 3. (0+1)* – (0, 1)*; 4. (0+1)* 011 – znamená súbor všetkých reťazí zložených z 0 a 1 a končiacich reťazou 011; 5. (a+b) (a+b+0+1)* znamená množinu všetkých reťazcov (0, 1, a, b)* počnúc a alebo b.
Základné definície lemy: 1) α + β = β + α 2) * = e 3) α + (β + γ) = (α + β) + γ 4) α(βγ) = (αβ)γ 5) α( β + γ) = αβ + αγ 6) (α + β)γ = αγ + βγ 7) αe = eα = α 8) α = 9) α+α* = α* 10) (α*)* = α* 11) α+α = α 12) α+ = α
Vzťah medzi RT a RM RM sú jazyky generované RT. Napríklad: x = a+b, y = c+d, x X = (a, b), y Y = (c, d), x + y X Y = (a, b, c, d). Reťazenie: xy XY = (ac, ad, bc, bd). k(u+o)t (k)(u, o)(t) = (veľryba, mačka) alebo podľa lemmy č. 5 a č. 6 k(u+o)t = veľryba + mačka (veľryba, mačka) . Iterácia: x = a, x* X* = (e, a, aaa, ...), t.j. x* = e + xxx + ...
Spojenie medzi RP a RM Iterácia zreťazenia a spojenia: (xy)* = e + xyxyxy + … (x + y)* = e + (x + y)(x + y) + … = = e + xx + xy + yx + yy + xxx + … Príklad: 0 + 1(0+1)* (0) ((1) (0, 1)*) = (0, 1, 10, 11, 100, 101, 110, 111… ). Zjednotenie je komutatívne: x + y = y + x Zreťazenie nie je: xy ≠ yx
Komunikácia medzi RM a RM Príklady priority: x + yz (x, yz), (x + y)z (xz, yz), x + y* (e, x, y, yyy, yyyy, ...), (x + y)* (e, x, y, xx, xy, yx, yy, xxx, ...), (xy)* (e, xyxy, ...), xy* (x, xyy, xyyy, ...). Nové lemmy: a* + e = a*; (a + e)* = a*; a*a* = a*; e* = e; atď.
Regulárne sústavy rovníc Rovnica s regulárnymi koeficientmi X = a. X + b má riešenie (najmenší pevný bod) a*b: aa*b + b = (aa* + e)b = a*b Sústava rovníc s regulárnymi koeficientmi: X 1 = α 10 + α 11 X 1 + α 12 X 2 + … + α 1 n. Xn X 2 = α 20 + α 21 X 1 + α 22 X 2 + … + α 2 n. Xn …………………………. . Xn = αn 0 + αn 1 X 1 + αn 2 X 2 + … + αnn. Xn Neznáme – Δ = (X 1, X 2, …, Xn).
Regulárne sústavy rovníc Algoritmus riešenia (Gaussova metóda): Krok 1. Nastavte i = 1. Krok 2. Ak i = n, prejdite na krok 4. V opačnom prípade napíšte rovnice pre Xi v tvare Xi = αXi + β (β = β0 + βi +1 Xi+1 + … + βn. Xn). Potom na pravej strane pre rovnice Xi+1, ..., Xn nahradíme Xi regulárnym výrazom α*β. Krok 3. Zvýšte i o 1 a vráťte sa na krok 2. Krok 4. Napíšte rovnicu pre Xn ako Xn = αXn + β. Prejdite na krok 5 (s i = n). Krok 5. Rovnica pre Xi je Xi = αXi + β. Napíšte na výstupe Xi = α*β do rovníc pre Xi– 1, …, X 1, pričom namiesto Xi dosaďte α*β. Krok 6. Ak i = 1, zastavte, inak znížte hodnotu i o 1 a vráťte sa na krok 5.
Transformácia DFA na RT Pre DFA M = (Q, Σ, δ, q 0, F) zostavíme systém s regulárnymi koeficientmi, kde Δ = Q: 1. množina αij: = ; 2. ak δ(Xi, a) = Xj, a Σ, potom αij: = αij + a; 3. ak Xi F alebo δ(Xi,) = HALT, potom αi 0: = e. Po vyriešení bude požadovaná PV X 1 = q 0.
Prevod DFA na RV Príklad: pre číslo s pevnou bodkou získame sústavu q 0 = + q 0 + sq 1 + pq 2 + dq 3 + q 4 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 Tu: s – znamienko čísla, s = „+“ + „–“; p – desatinná čiarka, p = "."; d – čísla, d = „0“ + „1“ + … + „9“.
Konverzia DFA na RT Riešenie: q 0 = *(sq 1 + pq 2 + dq 3 + q 4 +) = sq 1 + pq 2 + dq 3 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 = pq 2 + dq 3, q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4, q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = dq 3 + pq 4 + e, q 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4 + e. Z tretej rovnice: q 3 = dq 3 + pq 4 + e = d*(pq 4 + e). Zo štvrtej rovnice: q 4 = dq 4 + e = d*.
Konverzia DFA na RT Spätný zdvih: q 3 = d*(pq 4 + e) = d*(pd* + e), q 2 = dq 4 = dd*, q 1 = pq 2 + dq 3 = pdd * + dd *(pd* + e), q0 = sq 1 + pq 2 + dq 3 = s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Táto DFA teda zodpovedá RT s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Zjednodušme si to: s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e) = = spdd* + sdd*(pd* + e) + pdd* + dd*(pd* + e) = (s + e)(pdd* + dd*(pd* + e)) Pre kratší zápis môžete použiť kladnú iteráciu aa* = a*a = a+: (s + e)(pdd* + dd* (pd* + e)) = (s + e)(pd+ + d+pd* + d+)
Prevod DFA na RT Mapovanie grafu prechodovej funkcie DFA na základné operácie s regulárnymi výrazmi: q 0 a b a q 1 q 2 q 1 q 0 a+b a b ab q 2 a*
Prevod DFA na RT Zložitejšie kombinácie operácií: q 0 a q 1 b b b q 0 a q 2 q 1 (a + e)b c b q 0 q 2 ab(cab)* q 0 (a + b)* q 0 a q 1 aa* = a+ q 0 a q 1 a b a a a (ab)+ q 2 b q 1 c e + (a + b)c*
Konverzia DFA na RT Pre RT (s + e)(pd+ + d+(pd* + e)): q 0 p q 2 d s p q 1 d d q 3 d p q 4 d q 5 d
Programovanie RV Regulárne výrazy: Zabudované do mnohých programovacích jazykov (PHP, Java. Script, ...); Implementované ako zásuvné komponenty (napríklad trieda Regex pre platformu .NET). Rozdiely vo formách zápisu: x? = x + e x(1, 3) = x + xxx atď.
Programovanie RT Konštrukty triedy Regex (System. Text. Regular. Expressions): Symbolová interpretácia sekvencie Escape b Pri použití v hranatých zátvorkách zodpovedá symbolu “←” (u 0008) t, r, n, a, f, v Tab (u 0009), návrat vozíka (u 000 D), nový riadok (u 000 A) atď. c. X Riadiaci znak (napr. c. C je Ctrl+C, u 0003) e Escape (u 001 B) ooo ASCII znak v osmičke xhh ASCII znak v šestnástkovej sústave uhhhh Unicode znak Nasledujúci znak nie je špeciálny znak RT. Tento symbol sa musí použiť na zakódovanie všetkých špeciálnych znakov. Príklad (príklad ukazuje vzor a hľadaný reťazec, nájdené zhody sú v reťazci podčiarknuté): @"rnw+" – "rn. Sú tu dva riadky."
Programovanie RV podmnožín symbolov. Akýkoľvek znak okrem konca riadku (n) Akýkoľvek znak z množiny [^xxx] Akýkoľvek znak okrem znakov z množiny Akýkoľvek znak z rozsahu ] Odčítanie jednej množiny alebo rozsahu od inej p(meno) Akýkoľvek znak špecifikovaný Unicode názov kategórie P (názov) Akýkoľvek znak, ktorý nie je špecifikovaný v názve kategórie Unicode w Sada znakov použitých pri špecifikovaní identifikátorov W Sada znakov, ktoré sa nepoužívajú pri špecifikovaní identifikátorov s Medzery S Všetky okrem medzier d Čísla D Nečíslice Príklady : @". +" – "rn. Sú ntdva riadky"; @"+" – "0 xabcfx"; @"[^fx]+" – "0 xabcfx"; @"+" – "0 xabcfx"; @"[^a-f]+" – "0 xabcfx"; @"]+" – "0 xabcfx"; @"p(Lu)" – "Svetlá mesta"; // Lu – veľké písmená @"P(Lu)" – "Mesto"; @"p(is. azbuka)" – "ha. OS"; //Je. Cyrilika – ruské písmená
Programovanie PB Kotva ^, A Na začiatku riadku $, Z Na konci riadku alebo pred znakom "n" na konci riadku z Na konci riadku G Kde končí predchádzajúca zhoda b Hranica slova B Akákoľvek pozícia, ktorá nie je na hranici slova Príklady: @ "G(d)" – "(1)(3)(5)(9)"; // tri zhody (1), (2) a (3) @"bnS*ionb" – "darovanie národa"; @"Bendw*b" – "koniec posiela vydržať veriteľa".
Programovanie operácií RT (kvantifikátory) *, *? Iterácia +, +? Pozitívna iterácia? , ? ? Nula alebo jedna zhoda (n), (n)? Presne n sa zhoduje s (n, ), (n, )? Aspoň n sa zhoduje (n, m), (n, m)? Od n do m sa zhodujú príklady (prvé kvantifikátory sú chamtivé, hľadajú čo najviac prvkov, druhé sú lenivé, hľadajú čo najmenej prvkov): @"d(3, )" – "888 -5555 "; @"^d(3)" – "913 -913"; @"-d(3)$" – "913 -913"; @"5+? 5" – "888 -5555"; // tri zhody - 55, 55 a 55 @"5+5" - "888 -5555".
Programovanie RV Zoskupenie () Skupina, ktorá automaticky dostane číslo (? :) Neukladať skupinu (?) alebo (? "meno") Ak sa nájde zhoda, vytvorí sa pomenovaná skupina (?) alebo vymaže predtým definovanú skupinu skupina a (? "názov - názov") uloženie podreťazca medzi predtým definovanou skupinou a novou skupinou (? imnsx:) do novej skupiny (? imnsx:) Povolí alebo zakáže ktorúkoľvek z piatich (? –imnsx:) možných možností v skupine: i – nerozlišujú sa malé a veľké písmená; s – jeden riadok (potom „.“ je ľubovoľný znak); m – viacriadkový režim („^“, „$“ – začiatok a koniec každého riadku); n – nezachytávať nepomenované skupiny; x – vylúčte zo vzoru medzery bez špeciálnych znakov a za znak čísla (#) (? =) zahrňte komentáre Pozitívny výhľadový výrok s nulovou dĺžkou
Programovanie RT (? !) Negatívny výhľadový príkaz s nulovou dĺžkou (?) Nenávratná (nenásytná) časť výrazu Príklady: @"(an)+" – "bananas annals"; @"an+" – "banánové letopisy"; // porovnaj, tri zhody - an, an a ann @"(? i: an)+" - "ba. NAnas annals"; @"+(? =d)" – "abc xyz 12 555 w"; @"(?
Src="https://site/presentation/-112203859_437213351/image-24.jpg" alt="RV Programovanie Číslo odkazov Odkaz na skupinu k Odkaz na pomenovanú skupinu Príklady: @"> Программирование РВ Ссылки число Ссылка на группу k Ссылка на именованную группу Примеры: @"(w)1" – "deep"; @"(? w)k " – "deep". Конструкции изменения | Альтернатива (соответствует операции объединения) (? (выражение)да|нет) Сопоставляется с частью «да» , если выражение соответствует; в противном случае сопоставляется с необязательной частью «нет» (? (имя)да|нет), Сопоставляется с частью «да» , если названное имя (? (число)да|нет) захвата имеет соответствие; в противном случае сопоставляется с необязательной частью «нет» Пример: @"th(e|is|at)" – "this is the day";!}
Programovanie substitúcií RV $číslo Nahradí časť reťazca zodpovedajúcu skupine zadaným číslom $(meno) Nahradí časť reťazca zodpovedajúcu skupine zadaným názvom $$ Nahradí $ $& Nahradí kópiou celého reťazca match $` Nahradí text vstupného reťazca, kým sa nezhoduje s $" Nahradí text vstupných riadkov po zhode $+ Nahradiť poslednú zachytenú skupinu $_ Nahradiť celý riadok Komentáre (? #) Vložený komentár # Komentár na koniec riadku
Programovanie výsledkov RT Regex: Regex Matches() Match. Zbierka Match Groups() Group. Collection Group Captures() Capture. Zbierka zachytáva ()
Príklad programovania RV v C++ CLI (aplikácia konzoly Visual C++/CLR/CLR): int main() ( Regex ^r = gcnew Regex(L"((\d)+)+"); Zhoda ^m = r-> Zhoda (L"123 456"); int match. Count = 0; while (m->Success) ( Console: : Write. Line(L"Match (0)", ++match. Count); for (int i = 1; i Skupiny->Počet; i++) ( Skupina ^g = m->Skupiny[i]; Konzola: : Zápis. Riadok(L" Skupina (0) = "(1)"", i, g-> Hodnota ); for (int j = 0; j Zachytenie->Počet; j++) ( Zachytenie ^c = g->Zachytenie[j]; Konzola: : Zápis. Riadok(L" Zachytenie (0) = "(1)" , pozícia = (2), dĺžka = (3)", j, c, c->Index, c->Dĺžka); ) ) m = m->Ďalšia. Zhoda(); ) návrat 0; ) Systém: : Text : : Pravidelne. Výrazy
Povolenie akcií a hľadanie chýb Obmedzenie počtu platných číslic v čísle: (s + e)(pd+ + d+(pd* + e)) s = +|p = . d = ds + e = s? = (+|-)? pd* + e = (pd*)? = (.d*)? @"(+|-)? (. d+|d+(. d*)?)" alebo @"^(+|-)? (. d+|d+(. d*)?)$" Regulárny výraz r = nový regulárny výraz (@"^(+|-)? (. (? "číslica"d)+|(? "číslica"d)+(. (? "číslica"d)*)?)$"); Zhoda m = r. Match("+1. 23456789"); if (m. Úspech) ( Skupina g = m. Skupiny["číslica"]; if (g. Zachytí. Počet
Povolenie akcií a vyhľadávanie chýb Určenie polohy chyby: Regex r = nový Regex(@"(+|-)? (. (? "číslica"d)+|(? "číslica"d)+(. (? "číslica" d )*)?)"); string str = "+1. 2345!678"; Zhoda m = r. Match(str); if (m. Úspech) ( Skupina g = m. Skupiny["číslica"]; if (g. Zachytí. Počet 0) Konzola. Zápis. Riadok("Chyba na pozícii 1: neočakávaný znak "(0)"", str ); inak if (m. Dĺžka
Povolenie akcií a vyhľadávanie chýb Určenie polohy chyby: 1. prvá pozícia vstupného reťazca (1), ak prvá zhoda nezačína z pozície Index = 0; 2. pozícia nasledujúca po poslednej zhode (zhoda. Dĺžka + 1), ak sa nezhoduje s poslednou pozíciou vstupného reťazca; 3. poloha prvej medzery medzi zhodami (zhoda[i]. Index + zhoda[i]. Dĺžka + 1), ak znak nasledujúci po predchádzajúcej zhode nie je prvým znakom nasledujúcej zhody.
Index) zlom; index = m[i]. Index + m[i]. Dĺžka; ) Konzola. Napíšte. Riadok("Chyba na pozícii (0) "(1)"", index + 1, str); ) "abc. xyz. pqr" – správne; "+abc. xyz. pqr“ – chyba na pozícii 1 („+“); "abc. xyz. pqr! – chyba na pozícii 12 („!“); "abc. xyz!. pqr" – chyba na pozícii 8 ("!").
Povolenie akcií a vyhľadávanie chýb Ale! "abc. xyz. +pqr” – chyba na pozícii 8 (.”). Nová možnosť šablóny: @"w+(. w+)*(. (? !$))? " Overenie: "abc. xyz. +pqr“ – chyba na pozícii 9 („+“); "abc. xyz. pqr. " – chyba na pozícii 12 (".").
Vyvážené definície: "(? "x")" pridáva jeden prvok do kolekcie s názvom "x"; „(? „-x“)“ odstráni jeden prvok z kolekcie „x“; "(? (x)(? !))" skontroluje, či v kolekcii "x" nezostali žiadne prvky. Jazyk L popisujúci vnorené operátory Pascalu „začiatok koniec; ": @"^s*((? "začína+)+(? "-začína" končí*; s*)+)*(? (začína)(? !))$".
Je vhodnejšie opísať slovnú zásobu jazyka vo forme regulárnych výrazov a rozpoznať jazyk pomocou CA. Preto je dôležité vedieť previesť definície jazyka vo forme regulárnych výrazov na definíciu vo forme CA. Túto transformáciu navrhol Kenneth Thompson.
Konečný automat je päť (S, S, d, S 0 , F)
S je konečná množina stavov.
S je konečná množina platných vstupných signálov.
d - prechodová funkcia. Premieta množinu Sx(SÈ(e)) do množiny stavov nedeterministického konečného automatu. Pre deterministický automat funkcia prechodu odráža množinu SxS do množiny stavov automatu. Inými slovami, v závislosti od stavu a vstupného symbolu d určuje nový stav stroja.
S 0 - počiatočný stav konečného automatu, S 0 О S.
F je množina konečných stavov automatu, F О S.
Činnosť konečného automatu je postupnosť krokov. Krok je určený stavom stroja a vstupným symbolom. Samotný krok pozostáva zo zmeny stavu stroja a načítania ďalšieho symbolu vstupnej sekvencie.
Na prevod regulárnych výrazov na stavový automat platia nasledujúce pravidlá.
1 Regulárny výraz „e“ sa transformuje na automat dvoch stavov a e-prechod medzi nimi (obrázok 1).
Obrázok 1. – Automat na e-prechod
2 Regulárny výraz z jedného znaku „a“ sa na základe vstupného signálu a prevedie na konečný automat dvoch stavov a prechodu medzi nimi (obrázok 2).
Obrázok 2. – Automatický stroj na pohyb podľa symbolu a
3 Nech existuje regulárny výraz rs a konečné automaty pre výraz r a výraz s už boli zostavené. Potom sú dva stroje zapojené do série. Obrázok 3 zobrazuje pôvodné automaty pre jazyky r a s. Na obrázku je znázornený automat na rozpoznávanie zreťazenia týchto jazykov.
Stroj na r Stroj na s
Obrázok 3. – Počiatočné automaty
Obrázok 4. – Stroj na zreťazenie jazykov
4 Nech existuje regulárny výraz r | s a konečné automaty už boli zostrojené pre výraz r a výraz s (obrázok 3). Potom musí mať výsledný automat alternatívu k spusteniu jedného z dvoch automatov. Teda automat pre výraz r | s pre automaty pre r a s z obrázku 3 má tvar znázornený na obrázku 5.
Obrázok 5. – Automatický stroj na kombinovanie jazykov
5 Nech existuje regulárny výraz r* pre zostrojený konečný automat r. V tomto prípade sú zavedené dva nové stavy, aby bolo možné obísť výraz automat r, a tiež zaviesť e-prechod medzi konečným a počiatočným stavom, aby bolo možné automat r viackrát opakovať. Ak je pre regulárny výraz r skonštruovaný automat podobný obrázku 3, potom regulárny výraz r* zodpovedá konečnému automatu uvedenému na obrázku 6.
nastavenie
Podľa Kleeneovej vety akýkoľvek regulárny výraz môžete priradiť konečný stroj, ktorý je formálnym modelom algoritmu na rozpoznávanie lexém označených daným regulárnym výrazom. Najvšeobecnejšie povedané, štátny automat-rozpoznávač je určený konečnou množinou charakteristických stavov vstupného prúdu a prechodov medzi nimi. K zmene stavu dochádza, keď sú symboly vstupného toku prijaté z danej abecedy v súlade s prechodovou funkciou, ktorý na základe vstupného symbolu a aktuálneho stavu určuje možné následné stavy. Medzi možnými stavmi vyčnieva počiatočný(počiatočné) a konečná(dovoľovať) stavy, v ktorých môže byť rozpoznávač konečných automatov na začiatku a na konci spracovania tokenov vstupného toku. Ak vstupná sekvencia symbolov dokáže generovať sekvenciu prechodov, ktorá dokáže preniesť konečný automat z počiatočného stavu do jedného z koncových stavov, potom sa považuje za pripúšťajúci a patrí do ním rozpoznanej regulárnej množiny.
(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*
stôl 1
| 0 | 1 | |
| Q1 | Q4 | Q2 |
| Q2 | Q3 | Q1 |
| Q3 | Q2 | Q4 |
| Q4 | Q1 | Q3 |
Stĺpce tabuľky prechodu označujú znaky vstupnej abecedy a riadky zodpovedajú aktuálnym stavom DFA. Prvky každého riadku označujú stavy DFA, do ktorého musí prejsť z aktuálneho stavu po prijatí zodpovedajúcich znakov vstupnej abecedy. Najmä z prvého riadku tejto tabuľky prechodov vyplýva, že prijatie symbolov 0 a 1 v počiatočnom stave Q1 preloží DFA do stavov Q4 a Q2.
Pri rozpoznávaní vstupnej sekvencie pomocou tabuľky prechodov je ľahké sledovať zmeny v stave DFA s cieľom určiť, či je dosiahnutý jeden z povoľujúcich stavov alebo nie. Najmä pre binárny vektor 01001000 s párnym počtom núl a jednotiek je uvažovaná DFA generuje nasledujúcu postupnosť prechodov, kde každý prechod je označený symbolom vstupnej abecedy, ktorá ho spôsobuje:
Q1 0 Q4 1 Q3 0 Q2 0 Q3 1 Q4 1 Q1 0 Q4 0 Q1
Táto sekvencia prechodov končí pripúšťacím stavom Q1, preto binárny vektor 01001000 patrí do regulárnej množiny rozpoznávanej uvažovanou DFA a spĺňa vyššie uvedený regulárny výraz.
Na záver treba poznamenať, že uvažovaný neformálny spôsob konštruovania
Pre ďalšie štúdium vlastností konečných automatov a najmä pre riešenie úlohy syntézy je dôležitá nasledujúca veta.
Veta 7.7 (determinačná veta). Pre každý konečný automat možno zostrojiť ekvivalentný deterministický konečný automat.
Na dokázanie vety je potrebné najprv popísať algoritmus na zostrojenie deterministického konečného automatu z pôvodného; po druhé, ospravedlniť tento algoritmus dôsledným dokazovaním, že skutočne vytvára stavový stroj, ktorý je deterministický a ekvivalentný pôvodnému. Tu uvádzame iba algoritmus na konštrukciu deterministického automatu.
Transformácia ľubovoľného konečného automatu na ekvivalentný deterministický sa uskutočňuje v dvoch fázach: najprv sa odstránia oblúky s označením \lambda, potom sa vykoná samotná determinácia.
1. Odstránenie λ-prechodov (oblúky označené \lambda).
Ak chcete prejsť od pôvodného konečného automatu M=(V,Q,q_0,F,\delta) k ekvivalentnému konečnému automatu M"=(V,Q",q_0,F",\delta") bez λ-prechodov, stačí v origináli vykonať nasledujúce transformácie v grafe M.
A. Všetky stavy, okrem počiatočného, do ktorého vstupujú iba oblúky s označením \lambda, sú vymazané; čím definujeme množinu Q" konečného automatu M". Je jasné, že Q"\subseteq Q. Zároveň predpokladáme, že počiatočný stav zostáva rovnaký.
b. Množina oblúkov konečného automatu M" a ich návestí (teda prechodová funkcia M" ) je definovaná takto: pre ľubovoľné dva stavy p,r\in Q",~ p\to_(a)r nastáva vtedy a len ak a \in V , a v grafe M platí jedna z dvoch vecí: buď existuje oblúk od p do r, ktorého označenie obsahuje symbol a, alebo existuje stav q taký, že p\Rightarrow_(\lambda)^( +)q a q\ to_(a)r V tomto prípade vrchol q, všeobecne povedané, nemusí patriť do množiny Q“, t.j. môže zmiznúť pri prechode k automatu M" (obr. 7.11). Ak q\in Q" , potom, prirodzene, oblúk (q,r) zostane zachovaný v M" a symbol a bude jedným zo symbolov patriace k štítku tohto oblúka (obr. 7.12).
V M" sú teda uložené všetky oblúky M, ktorých označenia sú odlišné od \lambda a ktoré spájajú dvojicu (vrcholov) stavov z množiny Q" (nevymazané podľa časti a). Okrem toho, pre akúkoľvek trojicu stavov p,q,r (nemusí sa nevyhnutne líšiť!), takže p,r\in Q" a existuje cesta nenulovej dĺžky od p do q, ktorej označenie je rovnaké do \lambda (t.j. cesta po λ-prechodoch) a z q do r vedie oblúk, ktorého označenie obsahuje symbol a vstupnej abecedy; v M" je zostrojený oblúk z p do r, označenie ktorý obsahuje symbol a (pozri obr. 7.11).
V. Množina konečných stavov F" konečného automatu M" obsahuje všetky stavy q\in Q", teda stavy konečného automatu M, ktoré nie sú vymazané podľa odseku a, pre ktoré platí q\Rightarrow_(\lambda)^(\ ast) platí q_f pre nejaké q_f\in F (t.j. buď samotný stav q je konečným stavom konečného automatu M, alebo z neho vedie cesta nenulovej dĺžky po oblúkoch označených \lambda do jedného z konečných stavov konečný automat M) (obr. 7.13) .
2. Samotné určenie.
Nech M=(Q,V,q_0,F,\delta) je konečný automat bez λ-prechodov. Zostrojme deterministický konečný automat M_1 ekvivalentný M.
Tento konečný automat je definovaný tak, že jeho stavová množina je množinou všetkých podmnožín stavovej množiny konečného automatu M. To znamená, že každý jednotlivý stav konečného automatu M_1 je definovaný ako určitá podmnožina množiny stavov konečného automatu M. V tomto prípade je počiatočný stav nového konečného automatu (t.j. M_1) jednotónová podmnožina obsahujúca počiatočný stav starého konečného automatu (t.j. M) a konečné stavy nového konečného automatu sú všetky takéto podmnožiny. Q, ktoré obsahujú aspoň jeden konečný vrchol pôvodného konečného automatu M.
Odteraz, umožňujúc určitú slobodu prejavu, budeme niekedy stavy konečného automatu nazývať stavy-množiny M_1. Je však dôležité jasne pochopiť, že každý takýto stavový súbor je samostatným stavom nového konečného automatu, ale nie súborom jeho stavov. Zároveň je to pre pôvodný („starý“) konečný automat M práve množina jeho stavov. Obrazne povedané, každá podmnožina stavov starého konečného automatu sa „zrúti“ do jedného stavu nového konečného automatu*.
*Formálne by sme mali definovať množinu Q_1 ako množinu, ktorá je v priamej korešpondencii s množinou 2^Q, ale stále je pre nás pohodlnejšie predpokladať, že Q_1 sa zhoduje s 2^Q - koniec koncov, množinou stavov konečného automatu môže byť akákoľvek neprázdna konečná množina.
Prechodová funkcia nového konečného automatu je definovaná tak, že zo stavovej množiny S vstupným znakom a konečný automat M_1 prejde do stavovej množiny, ktorá je spojením všetkých stavov starého konečného automatu, do ktorého tento starý konečný automat ide podľa symbolu a z každej stavovej množiny S. Konečný automat M_1 je teda konštrukciou deterministický.
Vyššie uvedený slovný popis možno preložiť do vzorcov takto: zostavíme konečný stroj M_1 tak, že
M_1=(Q_1,V,\(q_0\),F_1,\delta_1) , kde
\begin(cases)Q_1=2^Q,\quad F_1=\(T\colon\, T\cap F\ne\varnothing,~T\in2^Q\),\\ (\forall S\subseteq Q) (\forall a\in V)\Bigl(\delta_1(S,a)= \bigcup\limits_(q\in S)\delta(q,a)\Bigr). \end(cases)
Venujme pozornosť tomu, že medzi stavmi nového konečného automatu je stav \varnothing , a podľa (7.8) \delta_1(\varnothing,a)=\varnothing pre ľubovoľný vstupný symbol a . To znamená, že v takomto stave ho stavový automat M_1 neopustí. Vo všeobecnosti platí, že akýkoľvek stav q konečného automatu taký, že pre ľubovoľný vstupný symbol a máme \delta(q,a)=q, sa nazýva absorbujúci stav konečného automatu. Teda stav \varnothing deterministického konečného automatu M_1 absorbuje. Je tiež užitočné poznamenať, že \delta_1(S,a)=\varnothing práve vtedy a len vtedy, ak pre každé q\in S (stavy starého konečného automatu z množiny stavov S ) \delta(q,a)= \varnothing , t.j. v grafe M nevyjde z každého takého stavu q žiadny oblúk označený symbolom a.
Dá sa dokázať, že konečný automat získaný pomocou takéhoto algoritmu je ekvivalentný pôvodnému.
Príklad 7.9. Určme konečný automat znázornený na obr. 7.14.
Ekvivalentný konečný automat bez λ-prechodov je znázornený na obr. 7.15. Všimnite si, že vrchol q_2 zmizne, pretože doň vstupujú iba „prázdne“ oblúky.
Na určenie výsledného automatu nie je vôbec potrebné zapisovať všetky jeho 2^3=8 stavy, z ktorých mnohé nemusia byť dosiahnuteľné z počiatočného stavu \(q_0\) . Na získanie stavov, ktoré sú dosiahnuteľné z \(q_0\), a iba z nich, použijeme takzvanú metódu ťahania.
Táto metóda môže byť všeobecne opísaná nasledovne.
V počiatočnom konečnom automate (bez prázdnych oblúkov) definujeme všetky množiny stavov, ktoré sú dosiahnuteľné z počiatočného, t.j. pre každý vstupný symbol a nájdeme množinu \delta(q_0,a) . Každá takáto množina v novom automate je stav priamo prístupný z pôvodného.
Pre každú z definovaných stavových množín S a každý vstupný symbol a nájdeme množinu \textstyle(\mathop(\bigcup\limits_(q\in S) \delta(q,a))\limits^(\phantom( A)^(.))). Všetky stavy získané v tomto kroku budú stavmi nového (deterministického) automatu, dosiahnuteľného z počiatočného vrcholu po dráhe dĺžky 2. Popísaný postup opakujeme dovtedy, kým sa neobjavia žiadne nové stavy množiny (vrátane prázdneho!). Dá sa ukázať, že takto vznikajú všetky stavy konečného automatu M_1, ktoré sú dosiahnuteľné z počiatočného stavu \(q_0\) .
Pre konečný automat na obr. 7.15 máme:
\begin(zarovnané)& \delta_1(\(q_0\),a)=\(q_1\);\qquad \delta_1(\(q_0\),b)=\(q_1,q_3\);\\ & \ delta_1(\(q_1\),a)=\(q_1\);\qquad \delta_1(\(q_1\),b)=\(q_1\);\\ & \delta_1(\(q_1,q_3\) ,a)= \delta(q_1,a)\pohár \delta(q_3,a)= \(q_1\)\pohár\(q_1\)=\(q_1\);\\ & \delta_1(\(q_1, q_3\),b)= \delta(q_1,b)\pohár \delta(q_3,b)= \(q_1\)\pohár\(q_1\)=\(q_1\). \end (zarovnané)
Keďže sa neobjavili žiadne nové množiny stavov, procedúra „ťahania“ tu končí a dostávame graf znázornený na obr. 7.16.
Pravidelné doplnenie jazykaJedným z dôležitých teoretických dôsledkov determinizačnej vety je nasledujúca veta.
Veta 7.8. Doplnkom regulárneho jazyka je regulárny jazyk.
Nech L je regulárny jazyk v abecede V. Potom doplnkom jazyka L (ako množiny slov) je jazyk \overline(L)=V^(\ast)\setminus L .
Podľa vety 7.7 možno pre regulárny jazyk L zostrojiť deterministický konečný automat M, ktorý pripúšťa L. Keďže v deterministickom automate je z každého vrcholu pre každý vstupný symbol definovaný prechod presne do jedného vrcholu, potom nech je reťazec x v abecede V akýkoľvek, existuje preň jedinečná cesta v M, začínajúc v počiatočnom stave, na ktorom reťazec x sa číta. Je jasné, že reťazec x je povolený automatom M , teda x\in L(M) , práve vtedy, ak je posledný stav zadanej cesty konečný. Z toho vyplýva, že reťazec x\notin L(M) práve vtedy, ak posledný stav zadanej cesty nie je konečný. Potrebujeme však len konečný automat M", ktorý pripúšťa reťazec x vtedy a len vtedy, ak to pôvodný konečný automat M neumožňuje. Následne, premenou každého konečného stavu M na nekonečný stav a naopak, dostaneme deterministický automat, ktorý pripúšťa pridanie jazyka L .
Osvedčená veta nám umožňuje zostaviť konečný automat, ktorý nepripúšťa určitú množinu reťazcov, pomocou nasledujúcej metódy: najprv postavíme automat, ktorý pripúšťa danú množinu reťazcov, potom ho určíme a ideme do automatu na sčítanie ako uvedené v dôkaze vety 7.8.
Príklad 7.10. A. Postavme konečný automat, ktorý akceptuje všetky reťazce v abecede \(0;1\) okrem reťazca 101.
Najprv postavme konečný automat, ktorý umožňuje jeden reťazec 101. Tento automat je znázornený na obr. 7.17.
Tento automat je kvázi-deterministický, ale nie deterministický, pretože nie je úplne definovaný. Určme ho a získame deterministický ekvivalentný konečný automat znázornený na obr. 7.18.
A nakoniec, prechodom na sčítanie (a premenovanie stavov), získame automat znázornený na obr. 7.19.
Všimnite si, že vo výslednom automate sú všetky vrcholy, okrem vrcholu s_3, konečné.
Všimnite si tiež, že prechod na doplnok, o ktorom sa hovorí v dôkaze vety 7.8, sa môže uskutočniť iba v deterministickom automate. Ak by sme si vymenili úlohy koncových a nefinálnych vrcholov v automate znázornenom na obr. 7.17, potom by sme dostali automat, ktorý pripúšťa jazyk \(\lambda,1,10\) , čo nie je - ako si možno ľahko predstaviť - množina všetkých reťazcov okrem reťazca 101.
Všimnite si tiež, že konečný automat na obr. 7.19 povoľuje všetky reťazce, ktoré obsahujú výskyt reťazca 101, ale nezhodujú sa s týmto reťazcom. Tu je napríklad reťazec 1011 nesúci cestu: s_0,s_1,s_2,s_3,t.
b. Postavme konečný automat, ktorý akceptuje všetky reťazce v abecede \(0;1\) okrem tých, ktoré obsahujú výskyt reťazca 101. Uvažujme jazyk L, ktorého každý reťazec obsahuje výskyt reťazca 101. Môže byť definované takto:
L=(0+1)^(\ast)101(0+1)^(\ast).
Potrebujeme postaviť automat na doplnenie jazyka L.
V tomto prípade priamo s použitím regulárneho výrazu je ľahké zostrojiť konečný automat, ktorý akceptuje jazyk L (obr. 7.20).
Potom vykonáme determináciu metódou „pull“. Výsledok stanovenia je znázornený na obr. 7.21.
Na úplné vyriešenie problému zostáva len obr. 7.21 zameniť úlohy koncových a nefinálnych vrcholov (obr. 7.22).
V. Poďme diskutovať o myšlienke zostrojiť konečný automat, ktorý umožňuje tie a len tie reťazce v abecede \(0;1\), ktoré nezačínajú reťazcom 01 a nekončia reťazcom 11 (t.j. reťazce tvar 01x a reťaze typu y11 nie sú povolené, nech už boli reťazce x,y\in\(0;1\) akékoľvek.
V tomto prípade je doplnkom jazyka, pre ktorý je potrebné zostrojiť konečný automat, množina všetkých takýchto reťazcov núl a jednotiek, ktoré začínajú reťazcom 01 alebo končia reťazcom 11. Automat, ktorý umožňuje túto množinu reťazce je skonštruovaný ako automat na kombinovanie 01(0+1)^(\ ast)+(0+1)^(\ast)11 rovnakým spôsobom, ako je opísané v dôkaze Kleeneovej vety (pozri vetu 7.6).
Z vlastnosti, že trieda regulárnych jazykov je uzavretá vzhľadom na doplnok (pozri Veta 7.8), okamžite vyplýva, že táto trieda je uzavretá vzhľadom na prienik, množinovú teóriu a symetrický rozdiel.
Dôsledok 7.3. Pre akékoľvek dva regulárne jazyky L_1 a L_2 platia nasledujúce tvrdenia:
1) priesečník L_1\cap L_2 je pravidelný;
2) rozdiel L_1\setmínus L_2 je regulárny;
3) symetrický rozdiel L_1\vartrojuholník L_2 je pravidelný.
Platnosť vyhlásení vyplýva z totožnosti:
\začiatok(zarovnané) &(\scriptstyle(\mathsf(1))))\quad L_1\cap L_2= \overline(\overline(L_1) \cup\overline(L_2))\,;\\ &(\scriptstyle (\mathsf(2))))\quad L_1\setminus L_2= L_1\cap \overline(L_2)\,;\\ &(\scriptstyle(\mathsf(3))))\quad L_1\,\trojuholník\ ,L_2 = (L_1\pohár L_2)\setmínus (L_1\cap L_2).\end(zarovnané)
Po prvé, získané výsledky nám umožňujú tvrdiť, že trieda regulárnych jazykov s ohľadom na operácie zjednotenia, prieniku a sčítania je booleovská algebra, v ktorej jednotkou je univerzálny jazyk a nula je prázdny jazyk. Po druhé, tieto algebraické vlastnosti rodiny regulárnych jazykov nám umožňujú vyriešiť dôležitý problém rozpoznania ekvivalencie dvoch ľubovoľných konečných automatov.
Podľa definície 7.10 sú konečné automaty ekvivalentné, ak sú jazyky, ktoré akceptujú, rovnaké. Preto na overenie ekvivalencie automatov M_1 a M_2 stačí dokázať, že symetrický rozdiel jazykov L(M_1) a L(M_2) je prázdny. Na to stačí skonštruovať automat, ktorý pripúšťa tento rozdiel a uistiť sa, že jazyk, ktorý pripúšťa, je prázdny. Vo všeobecnosti sa problém rozpoznania, že jazyk štátneho automatu je prázdny, nazýva problém prázdnoty štátneho automatu. Na vyriešenie tohto problému stačí nájsť množinu konečných stavov automatu, ktoré sú dosiahnuteľné z počiatočného stavu. Keďže konečný automat je orientovaný graf, tento problém možno vyriešiť napríklad pomocou vyhľadávania do šírky. Jazyk povolený konečným automatom je prázdny vtedy a len vtedy, ak je množina konečných stavov dosiahnuteľných z počiatočného stavu prázdna. V praxi je vhodnejšie rozpoznať ekvivalenciu konečných automatov pomocou minimalizačného algoritmu, ale teraz je pre nás dôležité zdôrazniť, že základná možnosť riešenia problému ekvivalencie vyplýva z vety 7.7 a jej algebraických dôsledkov.
