Lexikai elemzés. Szabályos nyelvek és véges állapotú gépek
az r bejegyzésben szereplő szimbólumok és műveleti jelek és zárójelek ábécéjének teljes karakterszámával.Alap. Az 1: és hosszúságú kifejezések automatái a következő ábrán láthatók.
Rizs. 5.1.
Vegye figyelembe, hogy mindhárom automata esetében a végső állapotok halmaza egyetlen állapotból áll.
Indukciós lépés. Most tegyük fel, hogy minden = 1 hosszúságú reguláris kifejezésre a w szó k részszóra osztható: w=w 1 w 2 ... w k és ennyi. Minden i= 1,... ,k esetén a w i szó q 0 1-et q f 1 -re fordítja. Ekkor a w szóhoz az M diagramban van egy út
Ennélfogva, . Megfordítva, ha egy szó q 0-t q f-re fordítja, akkor vagy létezik, vagy egy olyan út viszi, amely miután átment q 0-ból q 0 1-be, majd többször áthalad a q 0 1-ből q f 1-be tartó úton, és visszatér. q f 1-ből q 0 1-re átmenettel, végső soron q f 1-ből q f-ben végződik. Ezért egy ilyen szó.
A 4.2 és 5.1 tételből közvetlenül megkapjuk
Következmény 5.1. Minden reguláris kifejezéshez hatékonyan fel lehet építeni egy determinisztikus véges állapotú gépet, amely felismeri az adott kifejezés által képviselt nyelvet.
Ez az állítás a szintézistételek egyik példája: egy feladat leírása (a nyelv mint reguláris kifejezés) alapján hatékonyan felépül az azt végrehajtó program (DFA). Ennek fordítva is igaz - az elemzés tétele.
5.2. Tétel. Minden determinisztikus (vagy nem determinisztikus) véges állapotú géphez létre lehet hozni egy reguláris kifejezést, amely az adott gép által felismert nyelvet reprezentálja.
Ennek a tételnek a bizonyítása meglehetősen technikai jellegű, és meghaladja kurzusunk kereteit.
Így arra a következtetésre juthatunk, hogy a véges automata nyelvek osztálya egybeesik a reguláris nyelvek osztályával. Mostantól egyszerűen az automata nyelvek osztályának nevezzük.
Az M r automata, amelyet az 5.1. Tétel bizonyítása során konstruáltunk meg
Alapvető definíciók Az Σ ábécé reguláris kifejezései és az általuk jelölt reguláris halmazok rekurzív módon a következők szerint vannak definiálva: 1) – reguláris halmazt jelölő reguláris kifejezés; 2) e – reguláris halmazt jelölő reguláris kifejezés (e); 3) ha egy Σ, akkor a egy reguláris kifejezés, amely egy reguláris halmazt jelöl (a); 4) ha p és q reguláris kifejezések, amelyek P és Q reguláris halmazokat jelölnek, akkor a) (p+q) egy P Q-t jelölő reguláris kifejezés; b) pq – PQ-t jelölő reguláris kifejezés; c) p* – P*-t jelölő reguláris kifejezés; 5) semmi más nem reguláris kifejezés.
Alapvető definíciók Prioritás: * (iteráció) – legmagasabb prioritás; összefűzés; + (szakszervezet). Tehát 0 + 10* = (0 + (1 (0*))). Példák: 1. 01 jelentése (01); 2. 0* – (0*); 3. (0+1)* – (0, 1)*; 4. (0+1)* 011 – a 0-ból és 1-ből álló összes lánc halmaza, amely a 011-es lánccal végződik; 5. (a+b) (a+b+0+1)* az összes (0, 1, a, b)* a-val vagy b-vel kezdődő lánc halmazát jelenti.
A lemma alapvető definíciói: 1) α + β = β + α 2) * = e 3) α + (β + γ) = (α + β) + γ 4) α(βγ) = (αβ)γ 5) α( β + γ) = αβ + αγ 6) (α + β)γ = αγ + βγ 7) αe = eα = α 8) α = 9) α+α* = α* 10) (α*)* = α* 11) α+α = α 12) α+ = α
Az RT és az RM közötti kapcsolat Az RM az RT által generált nyelvek. Például: x = a+b, y = c+d, x X = (a, b), y Y = (c, d), x + y X Y = (a, b, c, d). Összefűzés: xy XY = (ac, ad, bc, bd). k(u+o)t (k)(u, o)(t) = (bálna, macska) vagy az 5. és 6. számú lemmák szerint k(u+o)t = bálna + macska (bálna, macska) . Iteráció: x = a, x* X* = (e, a, aaa, …), azaz x* = e + xxx + …
Az RP és az RM közötti kapcsolat Összefűzés és egyesülés iterációja: (xy)* = e + xyxyxy + … (x + y)* = e + (x + y)(x + y) + … = = e + xx + xy + yx + yy + xxx + … Példa: 0 + 1(0+1)* (0) ((1) (0, 1)*) = (0, 1, 10, 11, 100, 101, 110, 111… ). Az unió kommutatív: x + y = y + x Az összefűzés nem: xy ≠ yx
Kommunikáció az RM és az RM között Példák a prioritásra: 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, …). Új lemmák: a* + e = a*; (a + e)* = a*; a*a* = a*; e* = e; stb.
Szabályos egyenletrendszer Egyenlet reguláris együtthatókkal X = a. X + b-nek van megoldása (legkisebb fix pont) a*b: aa*b + b = (aa* + e)b = a*b Szabályos együtthatós egyenletrendszer: 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 Ismeretlenek – Δ = (X 1, X 2, …, Xn).
Szabályos egyenletrendszer Megoldási algoritmus (Gauss-módszer): 1. lépés Állítsa be i = 1. 2. lépés Ha i = n, folytassa a 4. lépéssel. Ellenkező esetben írja fel Xi egyenleteit Xi = αXi + β formában (β = β 0 + βi +1 Xi+1 + … + βn. Xn). Ezután a jobb oldalon az Xi+1, ..., Xn egyenleteknél Xi-t az α*β reguláris kifejezéssel helyettesítjük. 3. lépés: Növelje i-t 1-gyel, és térjen vissza a 2. lépéshez. 4. lépés: Írja fel az Xn egyenletét Xn = αXn + β alakban. Folytassa az 5. lépéssel (i = n esetén). 5. lépés: Xi egyenlete Xi = αXi + β. Írja be a kimenetre Xi = α*β, Xi– 1, …, X 1 egyenletébe, Xi helyett α*β-val helyettesítve. 6. lépés Ha i = 1, állítsa le, ellenkező esetben csökkentse az i-t 1-gyel, és térjen vissza az 5. lépéshez.
DFA átalakítása RT-vé DFA M = (Q, Σ, δ, q 0, F) esetén reguláris együtthatós rendszert alkotunk, ahol Δ = Q: 1. halmazd αij: = ; 2. ha δ(Xi, a) = Xj, a Σ, akkor αij: = αij + a; 3. ha Xi F vagy δ(Xi,) = HALT, akkor αi 0: = e. A megoldás után a kívánt PV X 1 = q 0 lesz.
DFA konvertálása RV-vé Példa: egy fixpontos számhoz a q 0 = + q 0 + sq 1 + pq 2 + dq 3 + q 4 q 1 = + q 0 + q 1 + pq 2 + dq 3 + rendszert kapjuk 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 Itt: s – a szám jele, s = „+” + „–”; p – tizedesvessző, p = "."; d – számok, d = „0” + „1” + … + „9”.
DFA konvertálása RT-vé Megoldás: 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. A harmadik egyenletből: q 3 = dq 3 + pq 4 + e = d*(pq 4 + e). A negyedik egyenletből: q 4 = dq 4 + e = d*.
DFA átalakítása RT-vé Fordított löket: q 3 = d*(pq 4 + e) = d*(pd* + e), q 2 = dq 4 = dd*, q 1 = pq 2 + dq 3 = pdd * + dd *(pd* + e), q 0 = négyzetméter + pq 2 + dq 3 = s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Így ez a DFA az RT s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e) RT-nek felel meg. Egyszerűsítsük: s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e) = = spdd* + sdd*(pd* + e)+ pdd* + dd*(pd* + e) = (s + e)(pdd* + dd*(pd* + e)) Rövidebb jelöléshez használhatja az aa* = a*a = a+ pozitív iterációt: (s + e)(pdd* + dd* (pd* + e)) = (s + e)(pd+ + d+pd* + d+)
DFA konvertálása RT-vé A DFA átmeneti függvény gráf leképezése alapvető műveletekre reguláris kifejezésekkel: q 0 a b a q 1 q 2 q 1 q 0 a+b a b ab q 2 a*
DFA átalakítása RT-vé Bonyolultabb műveletkombinációk: 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*
DFA átalakítása RT-vé RT esetén (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
RV programozás Reguláris kifejezések: Számos programozási nyelvbe beépítve (PHP, Java. Script, ...); Beépülő modulként valósítva meg (például a Regex osztály a .NET platformhoz). Különbségek a jelölési formák között: x? = x + e x(1, 3) = x + xxx stb.
A Regex osztály RT konstrukcióinak programozása (Rendszer. Szöveg. Szabályos. Kifejezések): Az Escape szekvencia szimbólumértelmezése b Ha szögletes zárójelben használjuk, a „←” szimbólumnak felel meg (u 0008) t, r, n, a, f, v Tab (u 0009), kocsi vissza (u 000 D), új sor (u 000 A) stb. c. X Vezérlőkarakter (pl. c. C a Ctrl+C, u 0003) e Escape (u 001 B) ooo ASCII karakter oktális formában xhh ASCII karakter hexadecimális uhhhh Unicode karakter A következő karakter nem speciális RT karakter. Ezt a szimbólumot kell használni, hogy elkerülje az összes speciális karaktert. Példa (a példa egy mintát és egy keresési karakterláncot mutat, a talált egyezések alá vannak húzva a karakterláncban): @"rnw+" – "rn. Itt két sor van."
RV szimbólumok részhalmazainak programozása. Bármely karakter, kivéve a sor végét (n) Bármely karakter a halmazból [^xxx] Bármely karakter, kivéve a készletből származó karaktereket Bármely karakter a tartományból ] Egy halmaz vagy tartomány kivonása egy másik p(név) bármely karakter, amelyet a Unicode határoz meg kategória nevű név P (név) A Unicode kategórianévben meghatározottaktól eltérő karakterek w Az azonosítók megadásához használt karakterek halmaza W Az azonosítók megadásához nem használt karakterek halmaza s Szóközök S Minden, kivéve a szóközöket d Számok D Nem számjegyek Példák : @". +" – "rn. Két sor van"; @"+" – "0 xabcfx"; @"[^fx]+" – "0 xabcfx"; @"+" – "0 xabcfx"; @"[^a-f]+" – "0 xabcfx"; @"]+" – "0 xabcfx"; @"p(Lu)" – "City Lights"; // Lu – nagybetűk @"P(Lu)" – "Város"; @"p(Is. Cirill)" – "ha. OS"; //Van. Cirill – orosz betűk
Programozás PB Anchor ^, A A $ sor elején, Z A sor végén vagy az "n" karakter előtt a sor végén z A sor végén G Ahol az előző egyezés véget ér b Szóhatár B Bármely pozíció, amely nem a szóhatáron Példák: @ "G(d)" – "(1)(3)(5)(9)"; // három egyezés (1), (2) és (3) @"bnS*ionb" – "nemzet adománya"; @"Bendw*b" – "vége küldi elviselni hitelező".
RT műveletek programozása (kvantifikátorok) *, *? Iteráció +, +? Pozitív iteráció? , ? ? Nulla vagy egy egyezés (n), (n)? Pontosan n egyezik (n, ), (n, )? Legalább n találat (n, m), (n, m)? n-től m-ig egyezik Példák (az első kvantorok mohók, minél több elemet keresnek, a másodikak lusták, a lehető legkevesebb elemet keresik): @"d(3, )" – "888 -5555 "; @"^d(3)" – "913 -913"; @"-d(3)$" – "913 -913"; @"5+? 5" – "888 -5555"; // három mérkőzés - 55, 55 és 55 @"5+5" - "888 -5555".
RV programozás Csoportosítás () Olyan csoport, amely automatikusan kap egy számot (? :) Ne mentse el a csoportot (?) vagy (? "név") Ha talál egyezést, létrejön egy elnevezett csoport (?) vagy Töröl egy korábban meghatározott csoportot csoport és (? "név - név") egy részkarakterlánc mentése egy új csoportban egy korábban meghatározott csoport és egy új csoport között (? imnsx:) Engedélyezi vagy letiltja az öt (? –imnsx:) lehetséges opció bármelyikét egy csoportban: i – nem érzékeny a kis- és nagybetűkre; s – egy sor (akkor a „.” bármilyen karakter); m – többsoros mód ("^", "$" - minden sor eleje és vége); n – ne rögzítsen névtelen csoportokat; x – a nem megtisztított szóközök kizárása a mintából, és megjegyzések szerepeltetése a számjel után (#) (? =) Nulla hosszúságú pozitív előretekintési utasítás
RT programozás (? !) Negatív nulla hosszúságú előretekintési utasítás (?) Egy kifejezés nem visszaadható (mohó) része Példák: @"(an)+" – "bananas annals"; @"an+" – "banan annals"; // összehasonlítás, három egyezés - an, an és ann @"(? i: an)+" - "ba. NAnas annals"; @"+(? =d)" – "abc xyz 12 555 w"; @"(?
Src="https://site/presentation/-112203859_437213351/image-24.jpg" alt="RV Programozási hivatkozások száma Link a csoporthoz k Hivatkozás a megnevezett csoporthoz Példák: @"> Программирование РВ Ссылки число Ссылка на группу k Ссылка на именованную группу Примеры: @"(w)1" – "deep"; @"(? w)k " – "deep". Конструкции изменения | Альтернатива (соответствует операции объединения) (? (выражение)да|нет) Сопоставляется с частью «да» , если выражение соответствует; в противном случае сопоставляется с необязательной частью «нет» (? (имя)да|нет), Сопоставляется с частью «да» , если названное имя (? (число)да|нет) захвата имеет соответствие; в противном случае сопоставляется с необязательной частью «нет» Пример: @"th(e|is|at)" – "this is the day";!}
RV helyettesítések programozása $szám Lecseréli a karakterláncnak a csoportnak megfelelő részét a megadott számra $(név) Lecseréli a csoportnak megfelelő részt a megadott néven $$ Helyettesít $ $& Lecseréli a teljes másolatra egyezés $` Addig cseréli a bemeneti karakterlánc szövegét, amíg az megegyezik: $" Lecseréli a bemeneti sorok szövegét egyezés után $+ Utoljára rögzített csoport cseréje $_ Teljes sor cseréje Megjegyzések (? #) Soron belüli megjegyzés # Megjegyzés a sor végéhez
A Regex RT eredményeinek programozása: Regex Matches() Match. Gyűjtemény Match Groups() Csoport. Gyűjtemény Group Captures() Capture. Gyűjtemény rögzítése()
RV programozási példa a C++ CLI-ben (Visual C++/CLR/CLR konzolalkalmazás): int main() ( Regex ^r = gcnew Regex(L"((\d)+)+"); Match ^m = r-> Match (L"123 456"); int egyezés. Szám = 0; while (m->Siker) ( Konzol: : Write. Line(L"Match (0)", ++match. Count); for (int i = 1; i Groups->Count; i++) ( Csoport ^g = m->Csoportok[i]; Konzol: : Írás. Line(L" Group (0) = "(1)", i, g-> Value ); for (int j = 0; j Captures->Count; j++) ( Capture ^c = g-> Captures[j]; Console: : Write. Line(L" Capture (0) = "(1)" , pozíció = (2), hossz = (3)", j, c, c->Index, c->Length); ) ) m = m->Next. Match(); ) return 0; ) Rendszer: : Szöveg : : Rendszeres. Kifejezések
Műveletek engedélyezése és hibák keresése Egy számban lévő jelentős számjegyek számának korlátozása: (s + e)(pd+ + d+(pd* + e)) s = +|p = . d = d s + e = s? = (+|-)? pd* + e = (pd*)? = (.d*)? @"(+|-)? (. d+|d+(. d*)?)" vagy @"^(+|-)? (. d+|d+(. d*)?)$" Regex r = új Regex (@"^(+|-)? (. (? "számjegy"d)+|(? "számjegy"d)+(. (? "számjegy"d)*)?)$"); Egyezés m = r. Match("+1. 23456789"); if (m. Siker) (g csoport = m. Csoportok["számjegy"]; if (g. Rögzítések. Szám
Műveletek engedélyezése és hibák keresése Hibapozíció meghatározása: Regex r = new Regex(@"(+|-)? (. (? "digit"d)+|(? "digit"d)+(. (? "digit") d)*)?)"); string str = "+1. 2345!678"; Egyezés m = r. Match(str); if (m. Siker) ( g csoport = m. Csoportok["számjegy"]; if (g. rögzítések. számlálás 0) konzol. Write. Line("Hiba az 1. pozícióban: váratlan karakter "(0)"", str ); else if (m. Hossz
Műveletek engedélyezése és hibakeresés A hiba helyének meghatározása: 1. a beviteli lánc első pozíciója (1), ha az első egyezés nem az Index = 0 pozícióból indul; 2. az utolsó egyezést követő pozíció (match. Length + 1), ha nem egyezik a beviteli lánc utolsó pozíciójával; 3. a mérkőzések közötti első rés helyzete (match[i]. Index + match[i]. Length + 1), ha az előző egyezést követő karakter nem a következő egyezés első karaktere.
Index) szünet; index = m[i]. Index + m[i]. Hossz; ) Konzol. Ír. Line("Hiba a (0) pozícióban "(1)"", index + 1, str); ) "abc. xyz. pqr" – helyes; "+abc. xyz. pqr” – hiba az 1. pozícióban („+”); "ABC. xyz. pqr! – hiba a 12. pozícióban („!”); "ABC. xyz!. pqr" – hiba a 8. pozícióban ("!").
Műveletek engedélyezése és hibakeresés De! "ABC. xyz. +pqr” – hiba a 8-as pozícióban (“.”). Új sablonopció: @"w+(. w+)*(. (? !$))? " Érvényesítés: "abc. xyz. +pqr” – hiba a 9-es pozícióban („+”); "ABC. xyz. pqr. " – hiba a 12. pozícióban (".").
Kiegyensúlyozott definíciók: "(? "x")" hozzáad egy elemet az "x" nevű gyűjteményhez; „(? „-x”)” eltávolít egy elemet az „x” gyűjteményből; Az "(? (x)(? !))" ellenőrzi, hogy nem maradt-e elem az "x" gyűjteményben. L nyelv, amely a Pascal beágyazott operátorait írja le „begin end; ": @"^s*((? "kezdődik+)+(? "-kezdődik"vége*; s*)+)*(? (kezdődik)(? !))$".
Kényelmesebb egy nyelv szókincsének leírása reguláris kifejezések formájában, és a nyelv felismerése a CA segítségével. Ezért fontos, hogy a reguláris kifejezések formájában lévő nyelvi definíciókat CA formátumú definícióvá alakíthassuk. Ezt az átalakítást Kenneth Thompson javasolta.
A véges állapotú gép öt (S, S, d, S 0, F)
S az állapotok véges halmaza.
S az érvényes bemeneti jelek véges halmaza.
d - átmeneti függvény. Az Sx(SÈ(e)) halmazt tükrözi egy nem determinisztikus véges automata állapothalmazába. Egy determinisztikus automata esetében az átmeneti függvény az SxS halmazt tükrözi az automata állapotok halmazába. Más szóval, az állapottól és a bemeneti szimbólumtól függően a d határozza meg a gép új állapotát.
S 0 - a véges automata kezdeti állapota, S 0 О S.
F az automata végállapotainak halmaza, F О S.
A véges állapotú gép működése lépések sorozata. A lépést a gép állapota és a bemeneti szimbólum határozza meg. Maga a lépés a gép állapotának megváltoztatásából és a beviteli sorozat következő szimbólumának beolvasásából áll.
A reguláris kifejezések állapotgéppé konvertálására a következő szabályok vonatkoznak.
1 Az „e” reguláris kifejezés két állapotú automatává és egy közöttük lévő e-átmenetté alakul (1. ábra).
1. ábra – Automatikus eszköz az elektronikus átálláshoz
2 Egy „a” karakterből álló reguláris kifejezés az a bemeneti jel alapján két állapotból és a köztük lévő átmenetből álló véges automatává alakul (2. ábra).
2. ábra – Automata mozgatáshoz a szimbólummal
3 Legyen egy rs reguláris kifejezés és az r kifejezéshez véges állapotú gépek és az s kifejezés már meg van építve. Ezután két gépet sorba kapcsolunk. A 3. ábra az r és s nyelvek eredeti automatáit mutatja. Az ábrán egy automata látható ezen nyelvek összefűzésének felismerésére.
Gép r Gép s
3. ábra – Kezdeti automaták
4. ábra – Nyelvösszefűző gép
4 Legyen egy r | reguláris kifejezés s és véges állapotú gépek már készültek az r kifejezésre és az s kifejezésre (3. ábra). Ekkor az eredményül kapott automatának kell lennie alternatívának a két automata valamelyikének végrehajtása helyett. Azaz egy automata az r | kifejezéshez A 3. ábrán látható r és s automaták s alakja az 5. ábrán látható.
5. ábra – Automata nyelvek kombinálására
5 Legyen r* reguláris kifejezés a megszerkesztett r véges automatára. Ebben az esetben két új állapot kerül bevezetésre, amelyek lehetővé teszik az r kifejezési automata megkerülését, valamint egy e-átmenetet vezetnek be a végső és a kezdeti állapot között, hogy lehetővé tegyék az r automata többszöri megismétlését. Ha az r reguláris kifejezésre a 3. ábrához hasonló automatát szerkesztünk, akkor az r* reguláris kifejezés a 6. ábrán bemutatott véges automatának felel meg.
Beállítások
Kleene tétele szerint bármely reguláris kifejezés társíthat egy véges gépet, amely az adott reguláris kifejezéssel jelölt lexémák felismerésére szolgáló algoritmus formális modellje. A legáltalánosabb értelemben egy állapotgép-a felismerőt a bemeneti folyam és a köztük lévő átmenetek jellemző állapotainak véges halmaza határozza meg. Állapotváltozás akkor következik be, amikor a bemeneti adatfolyam szimbólumait egy adott ábécétől kapjuk az átmeneti függvénynek megfelelően, amely a bemeneti szimbólum és az aktuális állapot alapján meghatározza a lehetséges további állapotokat. A lehetséges állapotok közül kiemelkedik a kezdeti(a kezdeti) és végleges(megengedve) állapotok, amelyekben a véges automata felismerő a bemeneti adatfolyam feldolgozási jogkivonatainak elején és végén lehet. Ha a bemeneti szimbólumsorozat képes egy olyan átmenet sorozatot generálni, amely át tudja vinni a véges állapotú gépet a kezdeti állapotból valamelyik végállapotba, akkor az elfogadónak minősül, és az általa felismert reguláris halmazhoz tartozik.
(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*
Asztal 1
| 0 | 1 | |
| Q1 | Q4 | Q2 |
| Q2 | Q3 | Q1 |
| Q3 | Q2 | Q4 |
| Q4 | Q1 | Q3 |
Az átmeneti táblázat oszlopai a bemeneti ábécé karaktereit jelzik, a sorok pedig a DFA aktuális állapotának felelnek meg. Az egyes sorok elemei a DFA állapotait jelzik, amelyre a bemeneti ábécé megfelelő karaktereinek vételekor át kell térnie az aktuális állapotból. Ennek az átmeneti táblázatnak az első sorából az következik, hogy a 0 és 1 szimbólumok Q1 kezdeti állapotban történő fogadása lefordítja a DFA-t. Q4 és Q2 állapotba.
Amikor egy bemeneti szekvenciát az átmeneti táblázat segítségével ismer fel, könnyen nyomon követhető a DFA állapotában bekövetkezett változások annak meghatározása érdekében, hogy az egyik engedélyező állapot megvalósul-e vagy sem. Különösen a páros számú nullát és egyest tartalmazó 01001000 bináris vektor esetében a figyelembe vett DFA a következő átmenet-sorozatot generálja, ahol minden egyes átmenetet az azt okozó bemeneti ábécé szimbóluma jelöl:
Q1 0 Q4 1 Q3 0 Q2 0 Q3 1 Q4 1 Q1 0 Q4 0 Q1
Ez az átmenetsorozat a Q1 engedélyezési állapottal végződik, ezért a 01001000 bináris vektor a vizsgált DFA által felismert reguláris halmazhoz tartozik.és kielégíti a fenti reguláris kifejezést.
Összegzésként meg kell jegyezni, hogy a számításba vett informális konstrukciós módszer
A véges automaták tulajdonságainak további tanulmányozásához és különösen a szintézis probléma megoldásához a következő tétel fontos.
7.7. tétel (determinációs tétel). Bármely véges automatához megszerkeszthető egy ekvivalens determinisztikus véges automata.
A tétel bizonyításához először is le kell írni azt az algoritmust, amellyel az eredetiből egy determinisztikus véges automatát készíthetünk; másodszor, igazolni ezt az algoritmust azzal, hogy szigorúan bebizonyítjuk, hogy valóban olyan állapotgépet hoz létre, amely determinisztikus és egyenértékű az eredetivel. Itt csak a determinisztikus automata felépítésének algoritmusát mutatjuk be.
Egy tetszőleges véges automata ekvivalens determinisztikusra transzformálása két lépésben történik: először eltávolítjuk a \lambda címkével ellátott íveket, majd magát a meghatározást hajtjuk végre.
1. λ-átmenetek eltávolítása (\lambda jelzésű ívek).
Ahhoz, hogy az eredeti M=(V,Q,q_0,F,\delta) véges automatától az M"=(V,Q",q_0,F",\delta") ekvivalens véges automatához λ-átmenetek nélkül eljussunk, elég az eredetiben hajtsa végre a következő átalakításokat az M gráfban.
A. Minden állapot törlődik, kivéve a kezdeti állapotot, amelybe csak a \lambda címkével ellátott ívek lépnek be; ezzel meghatározva az M" véges automata Q" halmazát. Egyértelmű, hogy Q"\subseteq Q. Ugyanakkor feltételezzük, hogy a kezdeti állapot változatlan marad.
b. Az M" véges automata íveinek halmazát és címkéit (ezáltal az M" átmeneti függvényt) a következőképpen definiáljuk: bármely két p,r\in Q állapotra,~ p\to_(a)r akkor és csak akkor következik be. ha a \in V , és az M gráfban két dolog teljesül: vagy van egy p-től r-ig tartó ív, amelynek címkéje az a szimbólumot tartalmazza, vagy van egy q állapot, hogy p\Rightarrow_(\lambda)^( +)q és q\ to_(a)r Ebben az esetben a q csúcs általában nem tartozik a Q" halmazhoz, azaz. eltűnhet az M" automatára való átlépéskor (7.11. ábra). Ha q\in Q" , akkor természetesen az ív (q,r) megmarad M"-ben, és az a szimbólum lesz az egyik szimbólum ennek az ívnek a címkéjéhez tartozó (7.12. ábra).
Így M"-ben minden olyan M ív tárolva van, amelyek címkéi különböznek a \lambda-tól, és amelyek a Q" halmaz állapotpárját (csúcsait) kapcsolják össze (az a rész szerint nem törölve). Ezen túlmenően bármely p,q,r (nem feltétlenül különböző!) állapotok hármasára úgy, hogy p,r\in Q" és van egy nullától eltérő hosszúságú út p-től q-ig, amelynek címkéje egyenlő \lambda-ba (azaz a λ-átmenetek általi út), és q-ból r-be egy ív vezet, amelynek címkéje a bemeneti ábécé a szimbólumát tartalmazza, M"-ben p-től r-ig ívet építünk, amely az a szimbólumot tartalmazza (lásd 7.11. ábra).
V. Az M" véges automata F" végállapotainak halmaza tartalmazza az összes q\in Q" állapotot, azaz az M véges automata azon állapotait, amelyek nem törlődnek az a) bekezdés szerint, amelyekre q\Rightarrow_(\lambda)^(\ ast) valamilyen q_f\in F-re q_f (vagyis vagy maga a q állapot az M véges automata végső állapota, vagy egy nullától eltérő hosszúságú út vezet belőle \lambda feliratú ívek mentén az automata egyik végállapotába véges automata M) (7.13. ábra) .
2. Maga az elhatározás.
Legyen M=(Q,V,q_0,F,\delta) véges automata λ-átmenetek nélkül. Szerkesszünk M_1 determinisztikus véges automatát, amely M-nek felel meg.
Ez a véges automata úgy van definiálva, hogy állapothalmaza az M véges automata állapothalmazának összes részhalmaza. Ez azt jelenti, hogy az M_1 véges automata minden egyes állapota az M véges automata állapothalmazának egy bizonyos részhalmazaként van definiálva. Ebben az esetben az új véges állapotú gép kezdeti állapota (azaz M_1) egy egyszemélyes részhalmaz, amely tartalmazza a régi véges állapotú gép (azaz M) kezdeti állapotát, és az új véges állapotú gép végső állapotai mind ilyen részhalmazok. Q amelyek tartalmazzák az eredeti M véges automata csúcsának legalább egy végpontját.
A továbbiakban, némi szólásszabadságot engedve, az M_1 véges automata állapotait néha állapothalmazoknak nevezzük. Fontos azonban világosan megérteni, hogy minden ilyen állapothalmaz egy új véges automata külön állapota, de nem állapothalmaza. Ugyanakkor az eredeti ("régi") M véges automata számára pontosan ez az állapotok halmaza. Képletesen szólva, a régi véges automata állapotainak minden részhalmaza „összeomlik” az új véges automata* egyik állapotába.
*Formálisan a Q_1 halmazt úgy kell meghatároznunk, mint egy olyan halmazt, amely egy az egyben megfelel a 2^Q halmaznak, de még mindig kényelmesebb azt feltételeznünk, hogy Q_1 egybeesik 2^Q-val - végül is a egy véges automata állapothalmaza tetszőleges nem üres véges halmaz lehet.
Az új véges automata átmeneti függvénye úgy van definiálva, hogy az S állapothalmazból az a bemeneti szimbólummal az M_1 véges automata az állapothalmazba kerül, amely a régi véges automata összes állapothalmazának uniója, amelybe ez a régi véges automata az a szimbólummal megy minden S állapothalmazból. Így az M_1 véges automata szerkezetileg determinisztikus.
A fenti szóbeli leírás a következőképpen fordítható le képletekre: építünk egy véges gépet M_1 úgy, hogy
M_1=(Q_1,V,\(q_0\),F_1,\delta_1) , ahol
\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(esetek)
Figyeljünk arra, hogy az új véges automata állapotai között van egy \varnothing állapot, és (7.8) szerint bármely a bemeneti szimbólumhoz \delta_1(\varnothing,a)=\varnothing. Ez azt jelenti, hogy ha egyszer ilyen állapotban van, az M_1 állapotgép nem hagyja el. Általánosságban elmondható, hogy egy véges automata bármely q állapotát, amelyben bármely a bemeneti szimbólumra \delta(q,a)=q van, a véges automata elnyelő állapotának nevezzük. Így az M_1 determinisztikus véges állapotgép \varnothing állapota elnyelő. Szintén hasznos megjegyezni, hogy \delta_1(S,a)=\varnothing akkor és csak akkor, ha minden q\in S esetén (a régi véges állapotú gép állapotai az S állapothalmazból) \delta(q,a)= \varnothing , azaz pl. az M gráfban nem lép ki ív minden ilyen a szimbólummal jelölt q állapotból.
Bizonyítható, hogy az ilyen algoritmussal kapott véges automata ekvivalens az eredetivel.
Példa 7.9. Határozzuk meg az ábrán látható véges automatát. 7.14.
ábrán egy ekvivalens véges automata látható λ-átmenetek nélkül. 7.15. Vegye figyelembe, hogy a q_2 csúcs eltűnik, mivel csak „üres” ívek lépnek be.
Az eredményül kapott automata meghatározásához egyáltalán nem szükséges felírni az összes 2^3=8 állapotát, amelyek közül sok nem érhető el a \(q_0\) kezdeti állapotból. A \(q_0\)-ból elérhető állapotok, és csak ezek megszerzéséhez az úgynevezett lehúzási módszert használjuk.
Ez a módszer általában a következőképpen írható le.
A kezdeti véges automatában (üres ívek nélkül) definiáljuk az összes állapothalmazt, amely a kezdeti állapotból elérhető, azaz. minden a bemeneti szimbólumhoz megtaláljuk a \delta(q_0,a) halmazt. Az új automatában minden ilyen halmaz egy állapot, amely közvetlenül elérhető a kezdeti állapotból.
Mindegyik definiált S állapotkészlethez és minden a bemeneti szimbólumhoz megtaláljuk a \textstyle(\mathop(\bigcup\limits_(q\in S) \delta(q,a))\limits^(\phantom( A)^( .))) . Az ebben a lépésben kapott összes állapot egy új (determinisztikus) automata állapota lesz, amely a kezdeti csúcsból 2 hosszúságú útvonalon érhető el. A leírt eljárást addig ismételjük, amíg új halmazállapotok (beleértve az üreset is!) nem jelennek meg. Megmutatható, hogy ez előállítja az M_1 véges automata összes olyan állapotát, amely a \(q_0\) kezdeti állapotból elérhető.
ábra véges állapotú gépére. 7.15 nálunk:
\begin(igazított)& \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)\cup \delta(q_3,a)= \(q_1\)\cup\(q_1\)=\(q_1\);\\ & \delta_1(\(q_1, q_3\),b)= \delta(q_1,b)\cup \delta(q_3,b)= \(q_1\)\cup\(q_1\)=\(q_1\). \end(igazított)
Mivel nem jelentek meg új állapothalmazok, a „húzási” eljárás itt véget is ér, és az ábrán látható grafikont kapjuk. 7.16.
Rendszeres nyelvi kiegészítésA determinizációs tétel egyik fontos elméleti következménye a következő tétel.
7.8. Tétel. A reguláris nyelv kiegészítése reguláris nyelv.
Legyen L egy reguláris nyelv az V ábécében. Ekkor az L nyelv kiegészítése (mint szavak halmaza) a \overline(L)=V^(\ast)\setminus L nyelv.
A 7.7. Tétel szerint egy L reguláris nyelvre egy M determinisztikus véges automata szerkeszthető, amely elfogadja L-t. Mivel egy determinisztikus automatában minden csúcsból minden bemeneti szimbólumra pontosan egy csúcsra van átmenet definiálva, akkor bármilyen legyen is az x lánc a V ábécében, van egy egyedi útja neki M-ben, amely abból a kezdeti állapotból indul ki, amelyen a x lánc beolvasva. Nyilvánvaló, hogy az x láncot az M automata, azaz x\in L(M) engedi meg, akkor és csak akkor, ha a megadott út utolsó állapota végleges. Ebből következik, hogy az x\notin L(M) lánc akkor és csak akkor, ha a megadott útvonal utolsó állapota nem végleges. De csak egy M" véges automatára van szükségünk, amely akkor és csak akkor enged be egy x láncot, ha azt az eredeti M véges automata nem teszi lehetővé. Következésképpen, ha M minden végső állapotát nem-végső állapottá változtatjuk, és fordítva, akkor kapunk egy determinisztikus automata, amely elfogadja az L nyelv hozzáadását.
A bizonyított tétel lehetővé teszi, hogy egy olyan véges automatát építsünk, amely nem enged be egy bizonyos lánchalmazt, a következő módszerrel: először készítünk egy automatát, amely beenged egy adott lánchalmazt, majd meghatározzuk azt, és az automatához megyünk az összeadáshoz. a 7.8. tétel bizonyítása szerint.
7.10. példa. A. Építsünk egy véges automatát, amely a \(0;1\) ábécé összes láncát elfogadja, kivéve a 101-es láncot.
Először is készítsünk egy véges automatát, amely egyetlen 101 láncot tesz lehetővé. Ezt az automatát a 1. ábra mutatja. 7.17.
Ez az automata kvázi determinisztikus, de nem determinisztikus, mivel nincs teljesen definiálva. Határozzuk meg, és kapjunk egy determinisztikus ekvivalens véges automatát, amely az ábrán látható. 7.18.
És végül az összeadásra (és az állapotok átnevezésére) lépve megkapjuk az ábrán látható automatát. 7.19.
Figyeljük meg, hogy az eredményül kapott automatában az s_3 csúcs kivételével minden csúcs végleges.
Vegyük észre azt is, hogy a komplementerre való átmenet, amelyről a 7.8. Tétel bizonyítása vonatkozik, csak determinisztikus automatában hajtható végre. Ha felcserélnénk a végső és nem végső csúcsok szerepét az ábrán látható automatában. 7.17, akkor egy olyan automatát kapunk, amely elfogadja a \(\lambda,1,10\) nyelvet, amely nem - ahogyan könnyen elképzelhető - nem az összes lánc halmaza, kivéve a 101-es láncot.
Vegyük észre azt is, hogy a véges állapotú gép az ábrán. A 7.19 engedélyezi az összes olyan karakterláncot, amely a 101-es karakterlánc előfordulását tartalmazza, de magával a karakterlánccal nem egyezik. Itt van például az 1011 útvonalat hordozó lánc: s_0,s_1,s_2,s_3,t.
b. Építsünk egy véges automatát, amely elfogadja a \(0;1\) ábécé összes láncát, kivéve azokat, amelyek tartalmazzák a 101 lánc előfordulását. Tekintsünk egy L nyelvet, amelynek minden lánca tartalmazza a 101 lánc előfordulását. az alábbiak szerint határozzák meg:
L=(0+1)^(\ast)101(0+1)^(\ast).
Egy automatát kell építenünk az L nyelv kiegészítésére.
Ebben az esetben a reguláris kifejezés közvetlen használatával könnyen megszerkeszthető egy véges automata, amely elfogadja az L nyelvet (7.20. ábra).
Ezután a meghatározást a „pull” módszerrel végezzük. A meghatározás eredménye az ábrán látható. 7.21.
A probléma teljes megoldásához csak az 1. ábrán látható. 7.21 felcseréli a végső és nem végső csúcsok szerepét (7.22. ábra).
V. Vizsgáljuk meg egy olyan véges automata felépítésének ötletét, amely az ábécé \(0;1\) azokat a láncait engedélyezi, amelyek nem a 01-es lánccal kezdődnek és nem érnek véget a 11-es lánccal (azaz a A 01x forma és az y11 típusú láncok nem megengedettek, függetlenül attól, hogy milyen láncok voltak x,y\in\(0;1\) ).
Ebben az esetben annak a nyelvnek a komplementere, amelyhez véges automatát kell készíteni, az összes olyan nullákból és egyesekből álló láncok halmaza, amelyek a 01-es lánccal kezdődnek, vagy a 11-es lánccal végződnek. A láncok egy automataként épülnek fel a 01(0+1)^(\ ast)+(0+1)^(\ast)11 kombinálására, a Kleene-tétel bizonyítása szerint (lásd a 7.6. tételt).
Abból a tulajdonságból, hogy a reguláris nyelvek osztálya a komplementre nézve zárt (lásd 7.8. Tétel), azonnal következik, hogy ez az osztály zárt a metszéspont, halmazelméleti és szimmetrikus különbség tekintetében.
Következmény 7.3. Bármely két reguláris L_1 és L_2 nyelvre a következő állítások igazak:
1) L_1\cap L_2 metszéspontja szabályos;
2) az L_1\setminus L_2 különbség szabályos;
3) az L_1\vartriangle L_2 szimmetrikus különbség szabályos.
Az állítások érvényessége az azonosságokból következik:
\begin(aligned) &(\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\,\triangle\ ,L_2 = (L_1\cup L_2)\setminus (L_1\cap L_2).\end(igazított)
Először is, a kapott eredmények lehetővé teszik, hogy kijelentsük, hogy a reguláris nyelvek osztálya az egyesülés, a metszés és az összeadás műveletei tekintetében egy Boole-algebra, amelyben az egység az univerzális nyelv, a nulla pedig az üres nyelv. Másodszor, a reguláris nyelvek családjának ezen algebrai tulajdonságai lehetővé teszik számunkra, hogy megoldjuk a két tetszőleges véges automata ekvivalenciájának felismerésének fontos problémáját.
A 7.10 definíció szerint a véges állapotú gépek ekvivalensek, ha az általuk elfogadott nyelvek megegyeznek. Ezért az M_1 és M_2 automaták egyenértékűségének ellenőrzéséhez elegendő bebizonyítani, hogy az L(M_1) és L(M_2) nyelvek szimmetrikus különbsége üres. Ehhez viszont elég egy olyan automatát megszerkeszteni, amely elismeri ezt a különbséget, és megbizonyosodni arról, hogy az általa elfogadott nyelv üres. Általában azt a problémát, hogy felismerjük, hogy egy állapotgép nyelve üres, az állapotgép ürességi problémájának nevezzük. A probléma megoldásához elég megkeresni az automata azon végállapotainak halmazát, amelyek a kezdeti állapotból elérhetők. Mivel a véges állapotú gép irányított gráf, ez a probléma megoldható például a szélességi kereséssel. Egy véges állapotú gép által megengedett nyelv akkor és csak akkor üres, ha a kezdeti állapotból elérhető végső állapotok halmaza üres. A gyakorlatban előnyösebb a véges automaták ekvivalenciáját minimalizáló algoritmussal felismerni, de most fontos hangsúlyoznunk, hogy az ekvivalencia-probléma megoldásának alapvető lehetősége a 7.7 Tételből és annak algebrai következményeiből következik.
