Lexikai elemzés. Szabályos nyelvek és véges automaták
az r rekordban szereplő szimbólumok ábécéjének és műveleti jeleinek és zárójeleinek összes 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 mind a három automata rendelkezik végső állapotok halmaza egy állapotból áll.
indukciós lépés. Tegyük fel most mindegyiknél ezt reguláris kifejezés hossz<= k
построен соответствующий
НКА, причем у него единственное заключительное состояние. Рассмотрим произвольное
reguláris kifejezés r hossza k+1 . Az utolsó művelettől függően három formája lehet: (r 1 + r 2), (r 1 r 2) vagy (r 1) * . Legyen és az L r1 és L r2 nyelveket felismerő NFA-k. Az általánosság elvesztése nélkül feltételezzük, hogy különböző állapotokkal rendelkeznek: 
.
Ezután az NFA , amelynek diagramja az ábrán látható. 5.2 , felismeri a nyelvet .
Rizs. 5.2.
Ennek a gépnek van állapotok halmaza, ahol q 0 egy új kezdeti állapot, q f egy új (egyedi!) végállapot, és a program M 1 és M 2 automata programokat és négy új átmeneti parancsot tartalmaz: . Nyilvánvaló, hogy az NFA M által felismert nyelv az L (M 1 ) és az L ( M 2 ) összes szót tartalmazza. Másrészt minden szó q 0 -t q f -be visz, és az első lépés után az azt hordozó út q 0 1-en vagy q 0 2 -n halad át. Mivel az M 1 és M 2 állapotok nem metszik egymást, így az első esetben ez az út csak a q f 1 -ből való -átmenettel juthat q f-be, majd 
. Hasonlóképpen a második esetben.
A kifejezéshez az L r nyelvet felismerő NFA diagramja a következő ábrán látható.
Rizs. 5.3.
Ennek a gépnek van állapotok halmaza 
, kezdeti állapot q 0 = q 0 1, végállapot q f =q f 2, és a program M 1 és M 2 automata programokat és egy új utasítást tartalmaz - átmenet az M 1 végállapotból az M 2 kezdeti állapotba, azaz. . Itt is nyilvánvaló, hogy a q 0 = q 0 1 és q f = q f 2 közötti bármely út áthalad q f 1 -ből q 0 2 -be. Ezért az M által engedélyezett bármely szó az L M1 ) egy szónak az L M2 ) szóval való összefűzése, és az ilyen szavak bármilyen összefűzése megengedett. Ezért az NFA M felismeri a nyelvet.
Legyen r = r 1 * . ábrán látható az L r =L r1* = L M1 * nyelvet felismerő NFA diagramja. 5.3.
Rizs. 5.3.
Ennek a gépnek van állapotok halmaza, ahol q 0 egy új kezdeti állapot, q f egy új (egyedi!) végállapot, és a program tartalmazza az M 1 automata programot és négy új átmeneti parancsot: . Nyilvánvalóan, . Egy nem üres w szóra az iteráció definíciója szerint 
néhány k >= 1 esetén 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ó leképezi q 0 1-et q f 1-re. Ekkor a w szóhoz az M diagramban van egy út
Következésképpen,. Megfordítva, ha egy szó q 0-t q f -re fordít, akkor vagy létezik, vagy a q 0 1 útvonal viszi át -átmenettel, végül q f 1 -ből az átmenet q f -re 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. Mindenkinek reguláris kifejezés hatékonyan megalkotható egy determinisztikus véges automata, amely felismeri a kifejezés által képviselt nyelvet.
Ez az állítás egy példa szintézis tételek: a feladatleírás szerint (nyelv mint reguláris kifejezés) egy olyan program (DFA), amely végrehajtja, hatékonyan felépül. Ez fordítva is igaz - elemzés tétele.
5.2. Tétel. Minden determinisztikus (vagy nem determinisztikus) véges automatához lehet konstruálni reguláris kifejezés, amely az automata által felismert nyelvet képviseli.
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 az osztállyal szabályos nyelvek. A következőkben egyszerűen úgy fogjuk nevezni automata nyelvek osztálya.
Az 5.1. Tétel bizonyítása során megszerkesztett M r automata
Alapvető definíciók A Σ á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 kifejezés, amely reguláris halmazt jelöl; 2) e egy reguláris kifejezés, amely egy reguláris halmazt (e) jelöl; 3) ha a Σ, akkor a az (a) reguláris halmazt jelölő reguláris kifejezés; 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 egy PQ-t jelölő reguláris kifejezés; c) p* egy 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 – az összes 0-ból és 1-ből álló, 011-es karakterláncra végződő karakterlánc halmaza; 5. (a+b) (a+b+0+1)* az összes a-val vagy b-vel kezdődő karakterlánc (0, 1, a, b)* halmazát jelenti.
A lemma fő definíciói: 1) α + β = β + α 2) * = e 3) α + (β + γ) = (α + β) + γ 4) α(βγ) = (αβ)γ 5 ) α( β + γ) = αβ + αγ 6) (α + β)γ = αγ + βγ 7) αe = eα = α 8) α = 9) α+α* = α* 10)*) (α*)*) = α* 11) α+α = α 12) α+ = α
Az RT és az RM kommunikációja 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)m = bálna + macska (bálna, macska) . Iteráció: x = a, x* X* = (e, a, aaa, …), azaz x* = e + xxx + …
RT és RM kapcsolata Ö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
Az RT és a PM kapcsolata Prioritási példák: 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 \u003d α 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 egyenletrendszerek 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 a következőképpen: Xi = αXi + β (β = β 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 = α*β, az Xi– 1, …, X 1 egyenletébe Xi helyett α*β-t 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 RW-vé DFA M = (Q, Σ, δ, q 0, F) esetén reguláris együtthatós rendszert alkotunk, ahol Δ = Q: 1. beállítjuk αij: = ; 2. ha δ(Xi, a) = Xj, a Σ, akkor αij: = αij + a; 3. ha Xi F vagy δ(Xi,) = HALT, akkor αi 0: = e. A kívánt RV megoldása után X 1 = q 0 lesz.
DFA konvertálása RW-vé Példa: fixpontos szám esetén 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 előjele, s = "+" + "–"; p – tizedesvessző, p = ". "; d - számok, d = "0" + "1" + ... + "9".
DFA-RW átalakítás 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 \u003d dq 3 + pq 4 + e \u003d d * (pq 4 + e). A negyedik egyenletből: q 4 = dq 4 + e = d*.
A DFA átalakítása RW-re fordított: 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 1 + pq 2 + dq 3 = s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Így ez a DFA megfelel a RE s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e) értéknek. Az egyszerűsítés kedvéért: 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-RT transzformáció A DFA átmeneti függvény gráfjának leképezése alapvető reguláris kifejezés műveletekre: 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-RW átalakítás RW-hez (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
Valós idejű programozás reguláris kifejezések: számos programozási nyelvbe beépítve (PHP, Java. Script, ...); Beépülő modulként implementálva (például Regex osztály a .NET platformhoz). Különbségek az írásformákban: x? = x + e x(1, 3) = x + xxx stb.
RT programozási reguláris kifejezés konstrukciók (Rendszer.Szöveg.Szabályos.kifejezések): Karakter Escape Sorozat értelmezése b Ha szögletes zárójelben használjuk, akkor megegyezik a "←" karakterrel (u 0008) t, r, n, a, f, v Tab (u 0009), kocsi vissza (u 000 D), új vonal (u 000 A) stb. c. X Vezérlőkarakter (például c. C a Ctrl+C, u 0003) e Escape (u 001 B) ooo Oktális ASCII karakter xhh Hex ASCII karakter uhhhh Unicode karakter A következő karakter nem speciális PB karakter. Minden speciális karaktert meg kell szökni ezzel a karakterrel. Példa (a példában a minta és a keresési karakterlánc adott, a karakterláncban talált egyezések alá vannak húzva): @"rnw+" – "rn. Itt n két karakterlánc található" .
RT programozása Karakterek részhalmazai. Bármely karakter, kivéve a karakterlánc 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évből) A Unicode által megadott bármely karakter kategória nevű név P (név) Bármilyen karakter, amely eltér a Unicode kategória névvel meghatározottaktól w 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 Szóközök kivételével bármi d Számjegyek D Nem számjegyek Példák: @ ". +" – "rn. Itt n két sor van"; @"+" - "0xabcfx"; @"[^fx]+" – "0 xabcfx"; @"+" - "0xabcfx"; @"[^a-f]+" – "0 xabcfx"; @"]+" – "0xabcfx"; @"p(Lu)" - "Város fényei"; // Lu - nagybetűk @"P(Lu)" - "Város"; @"p(cirill)" - "ha. OS"; // Is. Cirill - orosz betűk
PB programozási horgony ^, A A string elején $, Z A karakterlánc végén vagy a karakterlánc végén lévő "n" karakterig z A karakterlánc végén G Ahol az előző egyezés véget ért b Word határ B Bármely pozíció, amely nem a szóhatáron található. 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, a lehető legtöbb elemet keresik, 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".
RT Programozás Csoportosítás () A csoport automatikusan hozzárendelt egy számot (?:) Ne mentse el a csoportot (?) vagy (? "név") Ha talál egyezést, hozzon létre egy elnevezett csoportot (?) vagy Töröljön egy korábban meghatározott csoportot és (? "név-név") mentsen el az új csoportban egy részkarakterláncot a korábban meghatározott csoport és az új csoport között (? imnsx:) Be- vagy kikapcsolja a csoportban található öt lehetséges (? -imnsx:) opció bármelyikét: i - case érzéketlen; s egy sor (akkor a "." bármely karakter); m – többsoros mód („^” , „$” – minden sor eleje és vége); n - ne rögzítsen névtelen csoportokat; x - zárja ki a nem megtisztított szóközöket a mintából, és tegyen megjegyzéseket a számjel után (#) (?=) Nulla hosszúságú pozitív előretekintési állítás
RE programozás (? !) Nulla hosszúságú negatív előretekintési állítás (?) A kifejezés nem visszatérő (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://website/presentation/-112203859_437213351/image-24.jpg" alt="(!LANG:Programozás RT hivatkozási szám Csoporthivatkozás k Nevesített csoporthivatkozás Példák: @"> Программирование РВ Ссылки число Ссылка на группу k Ссылка на именованную группу Примеры: @"(w)1" – "deep"; @"(? w)k " – "deep". Конструкции изменения | Альтернатива (соответствует операции объединения) (? (выражение)да|нет) Сопоставляется с частью «да» , если выражение соответствует; в противном случае сопоставляется с необязательной частью «нет» (? (имя)да|нет), Сопоставляется с частью «да» , если названное имя (? (число)да|нет) захвата имеет соответствие; в противном случае сопоставляется с необязательной частью «нет» Пример: @"th(e|is|at)" – "this is the day";!}
RT programozási helyettesítések $szám Lecseréli a csoportnak megfelelő részt a megadott számra $(név) Lecseréli a csoportnak megfelelő részét a megadott névre $$ Helyettesítők $ $& Csere a teljes szöveg másolatára egyezés $` A bemeneti karakterlánc szövegének cseréje az egyezésig $" A bemeneti sor szövegének cseréje 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 programozási eredményei: Regex Matches() Match. Gyűjtemény Match Groups() Csoport. Gyűjtemény Group Captures() Capture. Gyűjtemény rögzítése()
RT 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: : Írás. 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éseket
Műveletek beillesztése és hibakeresés Egy számban lévő jelentős számjegyek számának korlátozása: (s + e)(pd+ + d+(pd* + e)) s = +|p = . d = ds + 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 A hiba helyének meghatározása: Regex r = new Regex(@"(+|-)? (. (? "digit"d)+|(? "digit"d)+(. (? ") számjegy"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.Length
Műveletek engedélyezése és hibakeresés A hiba helyének meghatározása: 1. a bemeneti karakterlá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 bemeneti karakterlánc utolsó pozíciójával; 3. a mérkőzések közötti első szünet 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-as pozícióban ("!").
Műveletek felvétele és hibakeresés De! "ABC. xyz. +pqr" - hiba a 8. pozícióban (". "). Új mintaváltozat: @"w+(. w+)*(. (? !$))? " Érvényesítés: "abc. xyz. +pqr" - hiba a 9. 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 nyelv beágyazott utasításait írja le: „begin end; ': @"^s*((? "kezdődik+)+(? "-kezdődik"vége*; s*)+)*(? (kezdődik)(? !))$".
Kényelmesebb egy nyelv szókincsét reguláris kifejezések formájában leírni, a nyelvet a KA segítségével felismerni. Ezért fontos, hogy a reguláris kifejezések formájában lévő nyelvi definíciókat FA formájú definícióvá alakíthassuk. Egy ilyen átalakítást Kennet Thompson javasolta.
Az állapotgép egy ötös (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 állapothalmazába. Más szóval, az állapottól és a bemeneti szimbólumtól függően d határozza meg az automata új állapotát.
S 0 - a véges automata kezdeti állapota, S 0 О S.
F az automata végállapotainak halmaza, F О S.
Az állapotgép működése lépések sorozata. A lépést az automata állapota és a bemeneti szimbólum határozza meg. Maga a lépés az automata állapotának megváltoztatásából és a bemeneti 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 - Automata az e-átmenethez
2 Egy „a” karakterből származó reguláris kifejezést két állapotból véges állapotú géppé alakítunk, és a köztük lévő átmenetet az a bemeneti jelnek megfelelően (2. ábra).
2. ábra - Automata a szimbólum alapján történő ugráshoz
3 Legyen egy rs reguláris kifejezés és az r kifejezéshez véges automaták és az s kifejezés már meg van építve. Ezután a két automatát sorba kötjük. A 3. ábra az r és s nyelvek kezdeti automatáit mutatja. Az ábrán egy automata látható ezen nyelvek összefűzésének felismerésére.
Automata r-hez Automatikus s-hez
3. ábra - Kezdeti automaták
4. ábra - Gép a nyelvek összefűzésére
4 Legyen egy r | reguláris kifejezés Az r kifejezésre és az s kifejezésre már felépítettek s és véges automatákat (3. ábra). Ekkor az eredményül kapott automatában kell lennie egy alternatívának a két automata egyikének végrehajtására. Vagyis az r | kifejezés automatája A 3. ábrán látható r és s automaták s alakja az 5. ábrán látható.
5. ábra - Gép nyelvek kombinálására
5 Legyen egy r* reguláris kifejezés a megszerkesztett r véges automatával. Ebben az esetben két új állapotot vezetünk be az r kifejezés automatája megkerülésének lehetőségére, és egy e-átmenetet vezetünk be a végső és a kezdeti állapot között az r automata többszöri ismétlődésének lehetőségére. Ha a 3. ábrához hasonló automatát építünk az r reguláris kifejezésre, akkor a 6. ábrán látható véges automata megfelel az r* reguláris kifejezésnek.
Beállítások
Kleene tétele szerint bármely reguláris kifejezés társítható egy véges automatához, amely az ezzel a reguláris kifejezéssel jelölt lexémák felismerésére szolgáló algoritmus formális modellje. A legáltalánosabb megfogalmazásban a véges automata-felismerőt a rá jellemző bemeneti folyam állapotok véges halmaza és a köztük lévő átmenetek határozzák meg. Állapotváltozás akkor következik be, amikor a bemeneti adatfolyam karaktereit egy adott ábécéből fogadjuk az átmeneti függvénynek megfelelően, amely meghatározza a bemeneti karakter és az aktuális állapot lehetséges további állapotait. A lehetséges állapotok közül kiemeljük a kezdeti (kezdeti) és végső (engedélyező) állapotokat, amelyekben az állapotgép-felismerő rendre a bemeneti folyam tokenek feldolgozásának elején, illetve befejezésekor lehet. Ha a bemeneti karaktersorozat képes egy olyan átmenet sorozatot generálni, amely át tudja vinni a véges automatát a kezdeti állapotból a végső állapotok egyikébe, 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ábla oszlopai a bemeneti ábécé karaktereit jelölik, a sorok pedig a DFA aktuális állapotának felelnek meg. Az egyes sorok elemei jelzik a DFA azon állapotait, amelyekbe a bemeneti ábécé megfelelő karaktereinek fogadásakor át kell térnie az aktuális állapotból. Ennek az átmeneti táblázatnak az első sorából különösen az következik, hogy a 0 és 1 szimbólumok fogadása a Q1 kezdeti állapotban a DFA-t a Q4 és Q2 állapotokba továbbítja.
Az átmeneti táblából a bemeneti szekvencia felismerésekor könnyen nyomon követhető a DFA állapotváltozásai annak megállapítása érdekében, hogy valamelyik elfogadó állapotot elértük-e vagy sem. Egy 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 hívó bemeneti ábécé karakterével jelölnek meg:
Q1 0 Q4 1 Q3 0 Q2 0 Q3 1 Q4 1 Q1 0 Q4 0 Q1
Ez az átmenetsorozat a Q1 elfogadó állapottal ér véget, 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, igazolja ezt az algoritmust azzal, hogy szigorúan bizonyítja, hogy valóban olyan véges automatát ad, amely determinisztikus és ekvivalens 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 a tényleges meghatározást.
1. λ-átmenetek eltávolítása (\lambda jelzésű ívek).
Elmozdulni az eredeti állapotgépről M=(V,Q,q_0,F,\delta) az egyenértékű véges automatához M"=(V,Q",q_0,F",\delta")λ-átmenetek nélkül elegendő a következő transzformációkat végrehajtani az eredeti M gráfban.
a. A kezdeti állapot kivételével, amelybe csak a \lambda feliratú ívek lépnek be, minden állapot eltávolításra kerül; ez határozza meg az M" véges automata Q" halmazát. Nyilvánvaló, hogy Q"\subseteq Q . Ebben az esetben feltételezzük, hogy a kezdeti állapot változatlan marad.
b. Az M" véges automata íveinek halmazát és címkéit (így az M" átmeneti függvényt) a következőképpen definiáljuk: bármely két állapotra p,r\in Q",~ p\to_(a)r akkor és csak akkor teljesül, ha a\in V , és a következők egyike teljesül az M gráfban: vagy létezik egy p-től r-ig terjedő ív, amelynek címkéje az a szimbólumot tartalmazza, vagy létezik olyan q állapot, p\Rightarrow_(\lambda)^(+)qés q\to_(a)r . Ebben az esetben a q csúcs általánosságban elmondható, hogy nem tartozik a Q "halmazhoz, azaz eltűnhet az M" automatához való átlépéskor (7.11. ábra). De ha q\in Q" , akkor természetesen az ív (q,r) megmarad M"-ben, és az a szimbólum lesz az egyik szimbólum, amely ennek az ívnek a címkéjéhez tartozik (7.12. ábra).
Így M"-ben minden olyan M ív tárolva van, amelyek címkéi eltérnek a \lambda-tól, és amelyek a Q" halmazból egy állapotpárt (csúcsokat) kapcsolnak össze (az a) pont szerint nem távolítják el). Ezenkívül a p,q,r állapotok bármely hármasára (nem feltétlenül különálló!), így p,r\in Q" és létezik egy nem nulla hosszúságú út p-től q-ig, amelynek címkéje egyenlő \lambda-val. (azaz az út λ-átmenetekkel), é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 egy ívet építünk, amelynek címkéje tartalmazza az a szimbólum (lásd 7.11. ábra).
ban ben. 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 tétel szerint, amelyekre vonatkozóan q\Rightarrow_(\lambda)^(\ast)q_f valamilyen q_f\in F esetén (vagyis vagy maga a q állapot az M véges automata végső állapota, vagy onnan van egy nullától eltérő hosszúságú út a \lambda feliratú ívek mentén a véges egyik végállapotába automata M ) (7.13. ábra).
2. Tulajdonképpen elszántság.
Hadd M=(Q,V,q_0,F,\delta) véges automata λ-átmenetek nélkül. Készítsünk egy ekvivalens determinisztikus véges automatát M_1 .
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 valamilyen részhalmazaként van definiálva. Ebben az esetben az új véges automata kezdeti állapota (azaz M_1 ) egy szingli részhalmaz, amely tartalmazza a régi véges automata kezdeti állapotát (azaz M ), az új véges automata végső állapotai pedig mind olyan Q részhalmazok, amelyek tartalmazzák legalább egy végső csúcsa az eredeti M véges automatának.
A továbbiakban, némi beszédszabadságot engedve, az M_1 véges automata állapotait néha állapothalmazoknak nevezzük. Fontos azonban világosan megérteni, hogy minden ilyen állapothalmaz az új véges automata külön állapota, de nem állapothalmaza. Ugyanakkor az eredeti ("régi") M véges automatánál 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 egy állapotába*.
*Formálisan a Q_1 halmazt úgy kell meghatározni, mint egy olyan halmazt, amely egy az egyben megfelel a 2^Q halmaznak, de még mindig kényelmesebb, ha figyelembe vesszük, hogy Q_1 egybeesik 2^Q-val, mert a halmaz egy véges automata állapotainak tetszőleges nem üres véges halmaza 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. amelyet ez a régi véges automata minden S állapothalmazból áthalad az a szimbólum mellett. Í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: az M_1 állapotgépet úgy építjük fel
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, \delta_1(\varnothing,a)=\varnothing bármely bemeneti karakterhez a . 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 állapotgép \varnothing állapota elnyelő. Azt is hasznos megjegyezni \delta_1(S,a)=\varnothing akkor és csak akkor, ha minden q\in S esetén (a régi véges automata állapotai az S állapothalmazból) \delta(q,a)=\varnothing, azaz az M gráfban minden ilyen q állapot nem hagy a szimbólummal jelölt ívet.
Bebizonyítható, hogy az ilyen algoritmussal kapott véges automata ekvivalens az eredetivel.
Példa 7.9.ábrán látható véges automatát határozzuk meg. 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.
A kapott automata meghatározásához egyáltalán nem szükséges kiírni az összes 2^3=8 állapotát, amelyek közül sok nem érhető el a \(q_0\) kezdeti állapotból. Ahhoz, hogy a \(q_0\) állapotokból elérhetõséget kapjunk, és csak ezek, az úgynevezett lehúzási módszert használjuk.
Ez a módszer általános esetben a következőképpen írható le.
Az eredeti véges automatában (üres ívek nélkül) definiáljuk az összes olyan állapothalmazt, amely a kezdeti állapotból elérhető, azaz. minden a bemeneti karakterhez 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.
Minden definiált S állapothalmazhoz és minden a bemeneti szimbólumhoz megtaláljuk a halmazt \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 egy 2 hosszúságú útvonalon érhető el. A leírt eljárást addig ismételjük, amíg új állapothalmazok (beleértve az üreset is) nem jelennek meg. Megmutatható, hogy ebben az esetben az M_1 véges automatának minden olyan állapota megkapható, 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 nincs több új állapothalmaz, a "húzási" eljárás itt véget ér, és a 2. ábrán látható grafikont kapjuk. 7.16.
Rendszeres nyelvi kiegészítés
A 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 nyelv \overline(L)=V^(\ast)\setminus L.
A 7.7. Tétel szerint egy L reguláris nyelvre egy M determinisztikus véges automata konstruálható, 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 karakterlánc a V ábécében, az M-ben van egy egyedi útvonal, amely a kezdőponttól kezdődik. állapot, amelyen az x karakterlánc olvasható. Nyilvánvaló, hogy az x karakterláncot az M automata, azaz az x\in L(M) , akkor és csak akkor engedélyezi, ha a megadott útvonal utolsó állapota végleges. Ez azt jelenti, 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 engedi meg az x láncot, ha az eredeti M véges automata ezt nem teszi lehetővé. Ezért M minden végállapotát nem véglegessé alakítva és fordítva, kapunk egy determinisztikus automata, amely lehetővé teszi az L nyelv befejezését.
A bizonyított tétel lehetővé teszi, hogy egy véges automatát hozzunk létre, amely nem engedélyez egy bizonyos lánchalmazt a következő módszerrel: először készítünk egy automatát, amely lehetővé teszi egy adott lánchalmazt, majd meghatározzuk azt, és átadjuk a komplementer automatának. amint azt a 7.8. tétel bizonyítása jelzi.
7.10. példa. a. Építsünk egy véges automatát, amely a \(0;1\) ábécé összes karakterláncát engedélyezi, kivéve a 101-es karakterláncot.
Először is készítünk egy véges automatát, amely egyetlen 101 láncot tesz lehetővé. Ez az automata a 1. ábrán látható. 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, áttérve az összeadásra (és átnevezve az állapotokat), 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éltük 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 - mint látható - nem minden karakterlánc halmaza, kivéve a 101-es karakterlá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-es láncot hordozó útvonal: s_0,s_1,s_2,s_3,t.
b. Készítsünk egy véges automatát, amely engedélyezi az összes karakterláncot az \(0;1\) ábécében, kivéve azokat, amelyek a 101 karakterlánc előfordulását tartalmazzák. Tekintsünk egy L nyelvet, amelynek minden karakterlánca tartalmazza a 101 karakterlá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.
Közvetlenül a reguláris kifejezésből ebben az esetben könnyen megszerkeszthető egy véges automata, amely lehetővé teszi az L nyelvet (7.20. ábra).
Ezután "húzós" módszerrel végezzük el a meghatározást. A meghatározás eredménye az ábrán látható. 7.21.
A probléma teljes megoldásához csak a 1. ábra. 7.21 felcseréli a végső és nem végső csúcsok szerepét (7.22. ábra).
ban ben. Beszéljük meg egy olyan véges automata felépítésének ötletét, amely lehetővé teszi az ábécé azon és csak azokat a karakterláncait \(0;1\), amelyek nem a 01-es karakterlánccal kezdődnek, és nem végződnek a 11-es karakterlánccal (azaz a A 01x és az y11 alakú karakterláncok nem megengedettek, bármilyen x,y\in\(0;1\) lánc is volt.
Ebben az esetben annak a nyelvnek a komplementere, amelyhez véges automatát szeretne építeni, az összes olyan nullák és egyesek halmaza, amelyek a 01-es karakterlánccal kezdődnek, vagy a 11-es karakterlánccal végződnek. Egy automata, amely elfogadja ezt a karakterlánc-készletet kombináló automataként van felépítve 01(0+1)^(\ast)+(0+1)^(\ast)11 ugyanúgy, mint a Kleene-tétel bizonyításakor (lásd 7.6. tétel).
A reguláris nyelvek osztályának komplementer alatti zárt tulajdonsága (lásd 7.8. Tétel) azonnal azt jelenti, hogy ez az osztály zárt metszéspontok, halmazelméleti és szimmetrikus különbségek esetén.
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) az L_1\cap L_2 metszés szabályos;
2) az L_1\setminus L_2 különbség szabályos;
3) szimmetrikus különbség L_1\vartriangle L_2 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, metszés és ö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 automaták ekvivalensek, ha az általuk engedélyezett nyelvek megegyeznek. Ezért az M_1 és M_2 automaták egyenértékűségének ellenőrzéséhez elegendő annak bizonyítása, hogy az L(M_1) és L(M_2) nyelvek szimmetrikus különbsége üres. Ehhez viszont elegendő egy olyan automatát megszerkeszteni, amely elismeri ezt a különbséget, és ellenőrizni kell, hogy az általa elfogadott nyelv üres-e. Általában azt a problémát, hogy felismerjük, hogy egy állapotgépi nyelv üres, állapotgép-ürességi problémának nevezzük. A probléma megoldásához elegendő megtalálni az automata azon végállapotainak halmazát, amelyek a kezdeti állapotból elérhetők. Mivel a véges állapotú gép egy irányított gráf, ez a probléma megoldható például a szélességi kereséssel. A véges automata által megengedett nyelv akkor és csak akkor üres, ha a kezdeti állapotból elérhető végá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.
