Lexikálna analýza. Regulárne jazyky a konečné automaty
celkovým počtom znakov abecedy symbolov a znakov operácií a zátvoriek v zázname 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 každý z týchto troch automatov má súbor konečných stavov pozostáva z jedného štátu.
indukčný krok. Predpokladajme teraz, že pre každého regulárny výraz dĺžka<= k
построен соответствующий
НКА, причем у него единственное заключительное состояние. Рассмотрим произвольное
regulárny výraz r dĺžky k+1. V závislosti od poslednej operácie môže mať jednu z troch foriem: (r 1 + r 2), (r 1 r 2) alebo (r 1) * . Nech a buďme NFA rozpoznávajúce jazyky L r1 a L r2 . Bez straty všeobecnosti budeme predpokladať, že majú rôzne stavy: 
.
Potom NFA, ktorého diagram je znázornený na obr. 5.2, rozpozná jazyk.
Ryža. 5.2.
Tento stroj má súbor štátov, kde q 0 je nový počiatočný stav, q f je nový (jedinečný!) konečný stav a program obsahuje programy automatov M 1 a M 2 a štyri nové prechodové príkazy: . Je zrejmé, že jazyk, ktorý rozpoznáva NFA M, zahŕňa všetky slová z L (M 1 ) az L ( M 2 ). Na druhej strane každé slovo trvá q 0 až q f a po prvom kroku cesta, ktorá ho vedie, prechádza cez q 0 1 alebo q 0 2 . Keďže sa stavy M 1 a M 2 nepretínajú, tak v prvom prípade sa táto cesta môže dostať do q f len -prechodom z q f 1 a potom 
. Podobne aj v druhom prípade.
Pre výraz je na nasledujúcom obrázku znázornený diagram NFA, ktorý rozpoznáva jazyk L r.
Ryža. 5.3.
Tento stroj má súbor štátov 
, počiatočný stav q 0 = q 0 1 , konečný stav q f = q f 2 a program obsahuje programy automatu M 1 a M 2 a jednu novú inštrukciu - prechod z konečného stavu M 1 do počiatočného stavu M 2, t.j. . Tu je tiež zrejmé, že akákoľvek cesta z q 0 = q 0 1 do q f = q f 2 prechádza cez prechod z q f 1 do q 0 2 . Preto každé slovo povolené M je zreťazením nejakého slova z L M1 ) s nejakým slovom z L M2 ) a akékoľvek zreťazenie takýchto slov je povolené. Preto NFA M rozpoznáva jazyk .
Nech r = r 1 * . Diagram NFA, ktorý rozpoznáva jazyk L r =L r1* = L M1 * je znázornený na obr. 5.3.
Ryža. 5.3.
Tento stroj má súbor štátov, kde q 0 je nový počiatočný stav, q f je nový (jedinečný!) konečný stav a program obsahuje program automatu M 1 a štyri nové prechodové príkazy: . Samozrejme, . Pre neprázdne slovo w podľa definície iterácie 
pre niektoré k >= 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 zobrazuje q 0 1 až q f 1 . Potom pre slovo w v diagrame M existuje cesta
V dôsledku toho, . Naopak, ak nejaké slovo prekladá q 0 na q f , tak buď existuje, alebo je vedené cestou q 0 1 -prechodom, prípadne 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ého regulárny výraz je možné efektívne skonštruovať deterministický konečný automat, ktorý rozpoznáva jazyk reprezentovaný týmto výrazom.
Toto vyhlásenie je jedným z príkladov teorémy syntézy: podľa popisu úlohy (jazyk ako regulárny výraz) efektívne skonštruovaný program (DFA), ktorý ho vykonáva. Opak je tiež pravdou - teorém analýzy.
Veta 5.2. Pre každý deterministický (alebo nedeterministický) konečný automat možno 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 dospieť k záveru, že trieda jazykov konečných automatov sa zhoduje s triedou regulárne jazyky. Ďalej to nazveme jednoducho trieda automatových jazykov.
Automat M r, ktorý je zostrojený 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, ktorý označuje regulárnu množinu; 2) e je 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 je regulárny výraz označujúci PQ; c) p* je 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á množinu všetkých reťazcov zložených z 0 a 1 a končiacich reťazcom 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.
Hlavné definície lemmy: 1) α + β = β + α 2) * = e 3) α + (β + γ) = (α + β) + γ 4) α(βγ) = (αβ)γ 5 ) α( β + γ) = αβ + αγ 6) (α + β)γ = αγ + βγ 7) αe = eα = α 8) α = 9) α+α* = α* 10) (α*)* = α* 11) α+α = α 12) α+ = α
Komunikácia 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 lemami č. 5 a č. 6 k(u+o)m = veľryba + mačka (veľryba, mačka) . Iterácia: x = a, x* X* = (e, a, aaa, ...), t.j. x* = e + xxx + ...
Vzťah RT 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
Vzťah medzi RT a PM 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 \u003d α 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 ako 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 ku kroku 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ýstup Xi = α*β, do rovníc pre Xi– 1, …, X 1 dosaďte α*β namiesto Xi. Krok 6. Ak i = 1, zastavte, inak znížte hodnotu i o 1 a vráťte sa na krok 5.
Transformácia DFA na RW Pre DFA M = (Q, Σ, δ, q 0, F) zostavíme sústavu s regulárnymi koeficientmi, kde Δ = Q: 1. nastavíme α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í požadovaného RV bude X 1 = q 0.
Prevod DFA na RW Príklad: pre číslo s pevnou bodkou dostaneme 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 je znamienko čísla, s = "+" + "-"; p – desatinná čiarka, p = "."; d - čísla, d = "0" + "1" + ... + "9".
Konverzia DFA na RW 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 \u003d dq 3 + pq 4 + e \u003d d * (pq 4 + e). Zo štvrtej rovnice: q 4 = dq 4 + e = d*.
Prevod DFA na RW Obrátený: 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á RE s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Pre zjednodušenie: 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+)
Transformácia DFA na RT Mapovanie grafu prechodovej funkcie DFA na základné operácie s regulárnym výrazom: 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 RW Pre RW (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
Regulárne výrazy programovania v reálnom čase: Zabudované do mnohých programovacích jazykov (PHP, Java. Script, …); Implementované ako zásuvné moduly (napríklad trieda Regex pre platformu .NET). Rozdiely v písaní: x? = x + e x(1, 3) = x + xxx atď.
Konštrukty triedy regulárneho výrazu programovania RT (System.Text.Regular.Expressions): Interpretácia sekvencie úniku znakov b Pri použití v hranatých zátvorkách sa zhoduje so znakom "←" (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íklad c. C je Ctrl+C, u 0003) e Escape (u 001 B) ooo Osmičkový znak ASCII xhh Hexadecimálny znak ASCII uhhhh Znak Unicode Nasledujúci znak nie je špeciálny znak PB. Všetky špeciálne znaky musia byť označené týmto znakom. Príklad (v príklade je uvedený vzor a hľadaný reťazec, nájdené zhody v reťazci sú podčiarknuté): @"rnw+" – "rn. Je tu n dvoch reťazcov" .
Programovanie RT Podmnožiny znakov. Akýkoľvek znak okrem konca reťazca (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 iného p(meno) Akýkoľvek znak špecifikovaný kódom Unicode názov kategórie P (názov) Akýkoľvek znak iný ako tie, ktoré špecifikuje názov 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 Čokoľvek okrem medzier d Číslice D Nie číslice Príklady: @ ". +" – "rn. Je tu n dvoch riadkov"; @"+" - "0xabcfx"; @"[^fx]+" – "0 xabcfx"; @"+" - "0xabcfx"; @"[^a-f]+" – "0 xabcfx"; @"]+" – "0xabcfx"; @"p(Lu)" - "Svetlá mesta"; // Lu - veľké písmená @"P(Lu)" - "Mesto"; @"p(je. azbuka)" - "ha. OS"; // Je. Cyrilika - ruské písmená
PB Programming Anchor ^, A Na začiatku reťazca $, Z Na konci reťazca alebo až po znak "n" na konci reťazca z Na konci reťazca G Kde skončila predchádzajúca zhoda b Slovo hranica 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".
Zoskupenie programovania RT () Skupine sa automaticky priradilo číslo (?:) Neukladať skupinu (?) alebo (? "meno") Ak sa nájde zhoda, vytvorte pomenovanú skupinu (?) alebo odstráňte predtým definovanú skupinu a (? "name-name") uložiť do novej skupiny podreťazec medzi predtým definovanou skupinou a novou skupinou (? imnsx:) Zapne alebo vypne ktorúkoľvek z piatich (? -imnsx:) možných možností v skupine: i - case necitlivý; s je 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účiť zo vzoru medzery bez špeciálnych znakov a za znak čísla (#) (?=) zahrnúť komentáre
RE programovanie (? !) Negatívne tvrdenie dopredu s nulovou dĺžkou (?) Nevracajúca sa (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://website/presentation/-112203859_437213351/image-24.jpg" alt="(!LANG:Programovanie RT Referenčné číslo 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 RT Substitúcie $čí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 $` Nahradiť text vstupného reťazca, kým sa nezhoduje $" Nahradiť text vstupného riadku po zhode $+ Nahradiť poslednú zachytenú skupinu $_ Nahradiť celý riadok Komentáre (? #) Vložený komentár # Komentár na koniec riadku
Výsledky programovania RT pre Regex: Regex Matches() Match. Zbierka Match Groups() Group. Collection Group Captures() Capture. Zbierka zachytáva ()
Príklad programovania RT 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: : Write.Line(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ýrazov
Zahrnutie 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 hľadanie chýb Určenie polohy chyby: Regulárny výraz r = nový regulárny výraz(@"(+|-)? (. (? "čí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, ak (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 od pozície Index = 0; 2. pozícia po poslednej zhode (zhoda. Dĺžka + 1), ak sa nezhoduje s poslednou pozíciou vstupného reťazca; 3. pozícia prvej prestávky 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. písať. Riadok("Chyba na pozícii (0) "(1)"", index + 1, str); ) "abc. xyz. pqr" je 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 ("!").
Zahrnutie akcií a hľadanie chýb Ale! "abc. xyz. +pqr" - chyba na pozícii 8 (."). Nový variant vzoru: @"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é príkazy jazyka Pascal „začiatok konca; ': @"^s*((? "začína+)+(? "-začína" končí*; s*)+)*(? (začína)(? !))$".
Je pohodlnejšie opísať slovnú zásobu jazyka vo forme regulárnych výrazov a rozpoznať jazyk pomocou KA. Preto je dôležité vedieť previesť definície jazyka vo forme regulárnych výrazov na definíciu vo forme FA. Takúto premenu navrhol Kennet Thompson.
Stavový automat je päťka (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 automatu.
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ť stavového automatu je postupnosť krokov. Krok je určený stavom automatu a vstupným symbolom. Samotný krok spočíva v zmene stavu automatu a načítaní ďalšieho symbolu vstupnej sekvencie.
Pre konverziu 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 pre e-prechod
2 Regulárny výraz z jedného znaku „a“ sa prevedie na konečný automat z dvoch stavov a prechodu medzi nimi podľa vstupného signálu a (obrázok 2).
Obrázok 2. - Automat na skákanie 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 sa dva automaty zapoja do série. Obrázok 3 zobrazuje počiatočné automaty pre jazyky r a s. Na obrázku je znázornený automat na rozpoznávanie zreťazenia týchto jazykov.
Automaticky pre r Automaticky pre 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 vo výslednom automate musí existovať alternatíva spustenia 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. - Stroj na kombinovanie jazykov
5 Nech existuje regulárny výraz r* so zostrojeným konečným automatom r. V tomto prípade sa zavádzajú dva nové stavy pre možnosť obídenia automatu výrazu r a zavádza sa e-prechod medzi koncovým a počiatočným stavom pre možnosť viacnásobného opakovania automatu r. Ak je pre regulárny výraz r zostavený automat podobný obrázku 3, potom konečný automat zobrazený na obrázku 6 zodpovedá regulárnemu výrazu r*.
nastavenie
Podľa Kleeneovej vety môže byť akýkoľvek regulárny výraz spojený s konečným automatom, ktorý je formálnym modelom algoritmu na rozpoznávanie lexém označených týmto regulárnym výrazom. Najvšeobecnejšie povedané, konečný automat-rozpoznávač je definovaný konečnou množinou preň charakteristických stavov vstupného toku a prechodov medzi nimi. K zmene stavu dochádza pri príjme znakov vstupného toku z danej abecedy v súlade s prechodovou funkciou , ktorá určuje možné následné stavy zo vstupného znaku a aktuálneho stavu. Medzi možnými stavmi sa vyčleňuje počiatočný (počiatočný) a konečný (povoľovací) stav, v ktorých môže byť stavový strojový rozpoznávač na začiatku a na konci spracovania tokenov vstupného toku. Ak vstupná sekvencia znakov dokáže vygenerovať sekvenciu prechodov, ktorá dokáže preniesť konečný automat z počiatočného stavu do jedného z koncových, potom sa považuje za pripúšťajúci a patrí do regulárnej množiny, ktorú rozpoznáva.
(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 predstavujú znaky vstupnej abecedy a riadky zodpovedajú aktuálnym stavom DFA. Prvky každého riadku označujú stavy DFA, do ktorých má prejsť z aktuálneho stavu pri prijatí zodpovedajúcich znakov vstupnej abecedy. Konkrétne z prvého riadku tejto tabuľky prechodov vyplýva, že prijímanie symbolov 0 a 1 v počiatočnom stave Q1 prenáša DFA do stavov Q4 a Q2, v tomto poradí.
Pri rozpoznávaní vstupnej sekvencie z tabuľky prechodov je ľahké sledovať zmeny stavu DFA, aby sa určilo, či je dosiahnutý jeden z akceptujúcich stavov alebo nie. Konkrétne pre binárny vektor 01001000 s párnym počtom núl a jednotiek uvažovaná DFA generuje nasledujúcu postupnosť prechodov, kde každý prechod je označený znakom vstupnej abecedy, ktorá ho volá:
Q1 0 Q4 1 Q3 0 Q2 0 Q3 1 Q4 1 Q1 0 Q4 0 Q1
Táto sekvencia prechodov končí akceptujúcim 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 opísať algoritmus na zostrojenie deterministického konečného automatu z pôvodného; po druhé, zdôvodnite tento algoritmus prísnym dôkazom, že skutočne poskytuje konečný automat, 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á vlastné určenie.
1. Odstránenie λ-prechodov (oblúky označené \lambda ).
Presun z pôvodného stavu automatu M=(V,Q,q_0,F,\delta) na ekvivalentný konečný automat M"=(V,Q",q_0,F"\delta") bez λ-prechodov stačí v pôvodnom grafe M vykonať nasledujúce transformácie.
a. Všetky stavy, okrem počiatočného stavu, do ktorých sa zadávajú iba oblúky označené \lambda , sú odstránené; toto definuje množinu Q" konečného automatu M" . Je jasné, že Q"\subseteq Q. V tomto prípade predpokladáme, že počiatočný stav zostáva rovnaký.
b. Množina oblúkov konečného automatu M" a ich označenia (teda prechodová funkcia M") je definovaná takto: pre ľubovoľné dva stavy p,r\in Q",~ p\to_(a)r platí práve vtedy, ak a\in V a v grafe M platí jedno z nasledujúcich: 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 vo všeobecnosti nemusí patriť do množiny Q", t.j. môže zmiznúť pri prechode k automatu M" (obr. 7.11). Ale ak q\in Q" , potom, prirodzene, oblúk (q,r) zostane zachovaný v M" a symbol a bude jedným zo symbolov patriacich k označeniu 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" (neodstránené podľa položky a). Okrem toho, pre akúkoľvek trojicu stavov p,q,r (nemusí byť nevyhnutne odlišné!), takže p,r\in Q" a existuje cesta s nenulovou dĺžkou od p do q, ktorej označenie sa rovná \lambda (t. j. dráha λ-prechodmi) a z q do r vedie oblúk, ktorého štítok obsahuje symbol a vstupnej abecedy, v M“ je zostrojený oblúk z p do r, ktorého štítok 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" , t.j. stavy konečného automatu M, ktoré nie sú vymazané podľa položky a, pre ktoré q\Rightarrow_(\lambda)^(\ast)q_f pre nejaké q_f\in F (to znamená, že buď samotný stav q je konečným stavom konečného automatu M , alebo z neho vedie cesta nenulovej dĺžky pozdĺž oblúkov označených \lambda do jedného z konečných stavov konečného automat M ) (obr. 7.13).
2. Vlastne odhodlanie.
Nechaj M=(Q,V,q_0,F,\delta) je konečný automat bez λ-prechodov. Zostrojme ekvivalentný deterministický konečný automat M_1 .
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 nejaká 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ými stavmi nového konečného automatu sú všetky také podmnožiny Q, ktoré obsahujú aspoň jeden konečný vrchol pôvodného konečného automatu M .
Odteraz, ponechajú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 mala byť množina Q_1 definovaná ako množina, ktorá je vo vzájomnej korešpondencii s množinou 2^Q , ale stále je pre nás pohodlnejšie uvažovať, že Q_1 sa zhoduje s 2^Q , pretože množina stavov konečného automatu môže byť ľubovoľná 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 prechádza do stavovej množiny, ktorá je zlúčením všetkých stavov starého konečného automatu, do ktorým tento starý konečný automat prechádza okolo symbolu a z každého stavového súboru S . Konečný automat M_1 je teda konštrukciou deterministický.
Vyššie uvedený slovný popis možno preložiť do vzorcov takto: stavový automat M_1 postavíme 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ý znak 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 stavového automatu M_1 absorbuje. Je tiež užitočné poznamenať, že \delta_1(S,a)=\varnothing práve 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 každý takýto stav q nezanechá žiadny oblúk označený symbolom a .
Dá sa dokázať, že konečný automat získaný takýmto algoritmom 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 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 absolútne nevyhnutné 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 dosiahnuteľného zo stavov \(q_0\) a iba z nich používame takzvanú metódu ťahania.
Túto metódu možno vo všeobecnom prípade opísať nasledovne.
V pôvodnom 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ý znak 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é množiny stavov (vrátane prázdneho). Dá sa ukázať, že v tomto prípade sa získajú všetky také 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 už neexistujú žiadne nové množiny stavov, procedúra „ťahania“ tu končí a dostávame graf znázornený na obr. 7.16.
Bežný jazykový doplnok
Jedný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 z každého vrcholu je pre každý vstupný symbol definovaný prechod presne na jeden vrchol, potom bez ohľadu na reťazec x v abecede V existuje preň jedinečná cesta v M začínajúc od počiatočného bodu. stav, v ktorom sa číta reťazec x. 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ý. To znamená, že reťazec x\notin L(M) práve vtedy, ak posledný stav zadanej cesty nie je konečný. Potrebujeme však konečný automat M", ktorý povoľuje reťazec x vtedy a len vtedy, ak to pôvodný konečný automat M neumožňuje. Premenou každého konečného stavu M na nefinálny a naopak, dostaneme deterministický automat, ktorý umožňuje dokončenie jazyka L .
Dokázaná veta nám umožňuje zostrojiť konečný automat, ktorý neumožňuje určitú množinu reťazcov, a to nasledovnou metódou: najprv postavíme automat, ktorý danú množinu reťazcov umožňuje, potom ho určíme a odošleme automatu pre doplnok. ako je uvedené v dôkaze vety 7.8.
Príklad 7.10. a. Zostavme konečný automat, ktorý umožňuje všetky reťazce v abecede \(0;1\) okrem reťazca 101.
Najprv skonštruujeme 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, keď prejdeme na sčítanie (a premenovanie stavov), dostaneme 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 prehodili úlohy konečných a nefinálnych vrcholov v automate znázornenom na obr. 7.17 by sme dostali automat, ktorý pripúšťa jazyk \(\lambda,1,10\) , čo nie je - ako je ľahké vidieť - množina všetkých reťazcov iných ako reťazec 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 so samotným reťazcom. Tu je napríklad cesta nesúca reťaz 1011: s_0, s_1, s_2, s_3, t.
b. Zostavme konečný automat, ktorý umožňuje 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.
Priamo z regulárneho výrazu je v tomto prípade jednoduché zostrojiť konečný automat, ktorý umožňuje jazyk L (obr. 7.20).
Potom metódou „ťahania“ vykonáme určenie. Výsledok stanovenia je znázornený na obr. 7.21.
Pre úplné vyriešenie úlohy stačí Obr. 7.21 zameňte úlohy koncových a nefinálnych vrcholov (obr. 7.22).
v. Poďme diskutovať o myšlienke zostrojenia konečného automatu, ktorý umožňuje 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ťazce v tvare y11 nie sú povolené, nech už boli reťazce x,y\in\(0;1\) ).
V tomto prípade je doplnkom jazyka, pre ktorý chcete zostaviť 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ý pripúšťa túto množinu reťazcov je konštruovaný ako automat na kombinovanie 01(0+1)^(\ast)+(0+1)^(\ast)11 rovnakým spôsobom ako pri dôkaze Kleeneovej vety (pozri vetu 7.6).
Vlastnosť triedy regulárnych jazykov uzavretá pod doplnkom (pozri vetu 7.8) okamžite znamená, že táto trieda je uzavretá pod priesečníkmi, množinami a symetrickými rozdielmi.
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 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é umožňujú, 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. Aby sme to urobili, stačí skonštruovať automat, ktorý pripúšťa tento rozdiel a overiť, či jazyk, ktorý pripúšťa, je prázdny. Vo všeobecnosti sa problém rozpoznania, že jazyk štátneho stroja je prázdny, nazýva problém prázdnoty štátneho stroja. 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.
