Leksička analiza. Regularni jezici i konačni automati
ukupnim brojem znakova abecede simbola i operacijskih znakova i zagrada u unosu r.Osnova. Automati za izraze duljine 1: i prikazani su na sljedećoj slici.
Riža. 5.1.
Imajte na umu da se za svaki od ova tri automata skup konačnih stanja sastoji od jednog stanja.
Indukcijski korak. Sada pretpostavimo da se za svaki regularni izraz duljine = 1, riječ w može podijeliti na k podriječi: w=w 1 w 2 ... w k i to je to. Za svaki i= 1,... ,k riječ w i prevodi q 0 1 u q f 1 . Tada za riječ w u dijagramu M postoji put
Stoga, . Obrnuto, ako neka riječ prevodi q 0 u q f, tada ili postoji ili je nosi put koji, nakon što je prošao od q 0 do q 0 1 i zatim prošao nekoliko puta duž puta od q 0 1 do q f 1 i vratio se od q f 1 do q 0 1 -prijelazom, u konačnici od q f 1 -prijelazom završava u q f . Stoga takva riječ.
Iz teorema 4.2 i 5.1 izravno dobivamo
Korolar 5.1. Za svaki regularni izraz može se učinkovito izgraditi deterministički konačni stroj koji prepoznaje jezik predstavljen tim izrazom.
Ova tvrdnja jedan je od primjera teorema sinteze: na temelju opisa zadatka (jezik kao regularni izraz) učinkovito se konstruira program (DFA) koji ga izvodi. Vrijedi i obrnuto - teorem analize.
Teorem 5.2. Za svaki deterministički (ili nedeterministički) konačni stroj moguće je konstruirati regularni izraz koji predstavlja jezik koji taj stroj prepoznaje.
Dokaz ovog teorema je prilično tehnički i izvan opsega našeg tečaja.
Dakle, možemo zaključiti da se klasa konačno automatskih jezika podudara s klasom regularnih jezika. Od sada ćemo to jednostavno zvati klasa automatskih jezika.
Automat M r, koji je konstruiran u dokazu teorema 5.1
Osnovne definicije Regularni izrazi u abecedi Σ i regularni skupovi koje oni označavaju definiraju se rekurzivno na sljedeći način: 1) – regularni izraz koji označava regularni skup; 2) e – regularni izraz koji označava regularni skup (e); 3) ako je a Σ, tada je a regularni izraz koji označava regularni skup (a); 4) ako su p i q regularni izrazi koji označavaju regularne skupove P i Q, tada je a) (p+q) regularni izraz koji označava P Q; b) pq – regularni izraz koji označava PQ; c) p* – regularni izraz koji označava P*; 5) ništa drugo nije regularni izraz.
Osnovne definicije Prioritizacija: * (iteracija) – najviši prioritet; ulančavanje; + (unija). Dakle, 0 + 10* = (0 + (1 (0*))). Primjeri: 1. 01 znači (01); 2. 0* – (0*); 3. (0+1)* – (0, 1)*; 4. (0+1)* 011 – označava skup svih lanaca sastavljenih od 0 i 1 koji završavaju lancem 011; 5. (a+b) (a+b+0+1)* označava skup svih lanaca (0, 1, a, b)* koji počinju s a ili b.
Osnovne definicije leme: 1) α + β = β + α 2) * = e 3) α + (β + γ) = (α + β) + γ 4) α(βγ) = (αβ)γ 5) α( β + γ) = αβ + αγ 6) (α + β)γ = αγ + βγ 7) αe = eα = α 8) α = 9) α+α* = α* 10) (α*)* = α* 11) α+α = α 12) α+ = α
Odnos između RT i RM RM su jezici koje generira RT. Na primjer: x = a+b, y = c+d, x X = (a, b), y Y = (c, d), x + y X Y = (a, b, c, d). Ulančavanje: xy XY = (ac, ad, bc, bd). k(u+o)t (k)(u, o)(t) = (kit, mačka) ili prema lemama br. 5 i br. 6 k(u+o)t = kit + mačka (kit, mačka) . Ponavljanje: x = a, x* X* = (e, a, aaa, …), tj. x* = e + xxx + …
Veza između RP i RM Iteracija ulančavanja i unije: (xy)* = e + xyxyxy + … (x + y)* = e + (x + y)(x + y) + … = = e + xx + xy + yx + yy + xxx + … Primjer: 0 + 1(0+1)* (0) ((1) (0, 1)*) = (0, 1, 10, 11, 100, 101, 110, 111… ). Unija je komutativna: x + y = y + x Ulančavanje nije: xy ≠ yx
Komunikacija između RM i RM Primjeri za prioritet: 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, …). Nove leme: a* + e = a*; (a + e)* = a*; a*a* = a*; e* = e; itd.
Regularni sustavi jednadžbi Jednadžba s regularnim koeficijentima X = a. X + b ima rješenje (najmanju fiksnu točku) a*b: aa*b + b = (aa* + e)b = a*b Sustav jednadžbi s pravilnim koeficijentima: 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 Nepoznato – Δ = (X 1, X 2, …, Xn).
Regularni sustavi jednadžbi Algoritam rješenja (Gaussova metoda): Korak 1. Postavite i = 1. Korak 2. Ako je i = n, idite na korak 4. U suprotnom, napišite jednadžbe za Xi u obliku Xi = αXi + β (β = β 0 + βi +1 Xi+1 + … + βn. Xn). Zatim, na desnim stranama jednadžbi Xi+1, ..., Xn, Xi zamijenimo regularnim izrazom α*β. Korak 3. Povećajte i za 1 i vratite se na korak 2. Korak 4. Napišite jednadžbu za Xn kao Xn = αXn + β. Idite na korak 5 (s i = n). Korak 5. Jednadžba za Xi je Xi = αXi + β. Zapišite na izlazu Xi = α*β, u jednadžbama za Xi– 1, …, X 1, zamjenjujući α*β umjesto Xi. Korak 6. Ako je i = 1, zaustavite se, inače smanjite i za 1 i vratite se na korak 5.
Transformacija DFA u RT Za DFA M = (Q, Σ, δ, q 0, F) sastavljamo sustav s pravilnim koeficijentima gdje je Δ = Q: 1. postavimo αij: = ; 2. ako je δ(Xi, a) = Xj, a Σ, onda je αij: = αij + a; 3. ako je Xi F ili δ(Xi,) = HALT, tada je αi 0: = e. Nakon rješavanja, željeni PV će biti X 1 = q 0.
Pretvaranje DFA u RV Primjer: za broj s fiksnom točkom dobivamo sustav 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 Ovdje: s – predznak broja, s = “+” + “–”; p – decimalna točka, p = "."; d – brojevi, d = “0” + “1” + … + “9”.
Pretvaranje DFA u RT Rješenje: 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. Iz treće jednadžbe: q 3 = dq 3 + pq 4 + e = d*(pq 4 + e). Iz četvrte jednadžbe: q 4 = dq 4 + e = d*.
Pretvorba DFA u RT Obrnuti hod: 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 = sq 1 + pq 2 + dq 3 = s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Prema tome, ovaj DFA odgovara RT s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Pojednostavimo: s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e) = = spdd* + sdd*(pd* + e) + pdd* + dd*(pd* + e) = (s + e)(pdd* + dd*(pd* + e)) Za kraću notaciju, možete koristiti pozitivnu iteraciju aa* = a*a = a+: (s + e)(pdd* + dd* (pd* + e)) = (s + e)(pd+ + d+pd* + d+)
Pretvaranje DFA u RT Preslikavanje grafa funkcije prijelaza DFA u osnovne operacije s regularnim izrazima: q 0 a b a q 1 q 2 q 1 q 0 a+b a b ab q 2 a*
Pretvaranje DFA u RT Složenije kombinacije operacija: 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*
Pretvorba DFA u RT Za RT (s + e)(pd+ + d+(pd* + e)): q 0 p q 2 d s p q 1 d d q 3 d p q 4 d q 5 d
RV programiranje Regularni izrazi: Ugrađeni u mnoge programske jezike (PHP, Java. Script, ...); Implementirano kao plug-in komponente (na primjer, klasa Regex za .NET platformu). Razlike u oblicima zapisa: x? = x + e x(1, 3) = x + xxx, itd.
Programiranje RT konstrukcija klase Regex (Sustav. Tekst. Regularni. Izrazi): Interpretacija simbola Escape sekvence b Kada se koristi u uglatim zagradama, odgovara simbolu “←” (u 0008) t, r, n, a, f, v Tab (u 0009), povratak na novi red (u 000 D), novi red (u 000 A) itd. c. X Kontrolni znak (npr. c. C je Ctrl+C, u 0003) e Escape (u 001 B) ooo ASCII znak u oktalnom xhh ASCII znak u heksadecimalnom uhhhh Unicode znak Sljedeći znak nije poseban RT znak. Ovaj simbol se mora koristiti za izbjegavanje svih posebnih znakova. Primjer (primjer prikazuje uzorak i niz za pretraživanje, pronađeni rezultati su podcrtani u nizu): @"rnw+" – "rn. Ovdje postoje dva retka."
Programiranje RV podskupova simbola. Bilo koji znak osim kraja retka (n) Bilo koji znak iz skupa [^xxx] Bilo koji znak osim znakova iz skupa Bilo koji znak iz raspona ] Oduzimanje jednog skupa ili raspona od drugog p(ime) Bilo koji znak određen Unicodeom naziv kategorije P (ime) Bilo koji znak osim onih navedenih u Unicode nazivu kategorije w Skup znakova koji se koriste u specificiranju identifikatora W Skup znakova koji se ne koriste u specificiranju identifikatora s Razmaci S Svi osim razmaka d Brojevi D Neznamenkasti primjeri : @". +" – "rn. Postoje ntdva retka"; @"+" – "0 xabcfx"; @"[^fx]+" – "0 xabcfx"; @"+" – "0 xabcfx"; @"[^a-f]+" – "0 xabcfx"; @"]+" – "0 xabcfx"; @"p(Lu)" – "Svjetla grada"; // Lu – velika slova @"P(Lu)" – "Grad"; @"p(Je. ćirilica)" – "ha. OS"; //Je. Ćirilica – ruska slova
Programiranje PB Sidro ^, A Na početku retka $, Z Na kraju retka ili prije znaka "n" na kraju retka z Na kraju retka G Gdje završava prethodno podudaranje b Granica riječi B Bilo koji položaj koji nije na granici riječi Primjeri: @ "G(d)" – "(1)(3)(5)(9)"; // tri utakmice (1), (2) i (3) @"bnS*ionb" – "donacija nacije"; @"Bendw*b" – "end šalje podnijeti zajmodavca".
Programiranje RT operacija (kvantifikatori) *, *? Ponavljanje +, +? Pozitivna iteracija? , ? ? Ništa ili jedno podudaranje (n), (n)? Točno n odgovara (n, ), (n, )? Barem n odgovara (n, m), (n, m)? Od n do m odgovara Primjeri (prvi kvantifikatori su pohlepni, traže što više elemenata, drugi su lijeni, traže što manje elemenata): @"d(3, )" – "888 -5555 "; @"^d(3)" – "913 -913"; @"-d(3)$" – "913 -913"; @"5+? 5" – "888 -5555"; // tri podudaranja - 55, 55 i 55 @"5+5" - "888 -5555".
RV programiranje Grupiranje () Grupa koja automatski prima broj (? :) Nemojte spremati grupu (?) ili (? "ime") Ako se pronađe podudaranje, kreira se imenovana grupa (?) ili Izbrišite prethodno definiranu grupa i (? "ime - ime") spremanje u novu grupu podniza između prethodno definirane grupe i nove grupe (? imnsx:) Omogućuje ili onemogućuje bilo koju od pet (? –imnsx:) mogućih opcija u grupi: i – neosjetljivo na velika i mala slova; s – jedan red (tada je “.” bilo koji znak); m – višeredni način (“^”, “$” – početak i kraj svakog retka); n – ne hvataj neimenovane grupe; x – isključi razmake bez izlaza iz uzorka i uključi komentare nakon znaka broja (#) (? =) Izjava pozitivnog pregleda unaprijed nulte duljine
RT programiranje (? !) Negativna izjava unaprijed nulte duljine (?) Nepovratni (pohlepni) dio izraza Primjeri: @"(an)+" – "bananas annals"; @"an+" – "ljetopis banane"; // usporedi, tri podudaranja - an, an i ann @"(? i: an)+" - "ba. NAnas anals"; @"+(? =d)" – "abc xyz 12 555 w"; @"(?
Src="https://site/presentation/-112203859_437213351/image-24.jpg" alt="RV programske veze broj Veza na grupu k Veza na imenovanu grupu Primjeri: @"> Программирование РВ Ссылки число Ссылка на группу k Ссылка на именованную группу Примеры: @"(w)1" – "deep"; @"(? w)k " – "deep". Конструкции изменения | Альтернатива (соответствует операции объединения) (? (выражение)да|нет) Сопоставляется с частью «да» , если выражение соответствует; в противном случае сопоставляется с необязательной частью «нет» (? (имя)да|нет), Сопоставляется с частью «да» , если названное имя (? (число)да|нет) захвата имеет соответствие; в противном случае сопоставляется с необязательной частью «нет» Пример: @"th(e|is|at)" – "this is the day";!}
Programiranje RV zamjena $number Zamjenjuje dio niza koji odgovara grupi navedenim brojem $(ime) Zamjenjuje dio niza koji odgovara grupi s navedenim imenom $$ Zamjenjuje $ $& Zamjenjuje kopijom punog match $` Zamjenjuje tekst ulaznog niza dok se ne podudara s $" Zamjenjuje tekst ulaznih redaka nakon podudaranja $+ Zamjena posljednje snimljene grupe $_ Zamjena cijelog retka Komentari (? #) Inline komentar # Komentar na kraj retka
Programiranje RT rezultata Regex-a: Regex Matches() Match. Skupina podudaranja zbirke() Grupa. Skupna zbirka Captures() Capture. Snimke zbirke ()
Primjer programiranja RV u C++ CLI (Visual C++/CLR/CLR konzolna aplikacija): int main() ( Regex ^r = gcnew Regex(L"((\d)+)+"); Match ^m = r-> Match (L"123 456"); int match. Count = 0; while (m->Success) ( Console: : Write. Line(L"Match (0)", ++match. Count); for (int i = 1; i Grupe->Broj; i++) ( Grupa ^g = m->Grupe[i]; Konzola: : Zapiši. Redak(L" Grupa (0) = "(1)"", i, g-> Vrijednost ); for (int j = 0; j Captures->Captures; j++) ( Capture ^c = g->Captures[j]; Konzola: : Write. Line(L" Capture (0) = "(1)" , pozicija = (2), duljina = (3)", j, c, c->Indeks, c->Dužina); ) ) m = m->Sljedeći. Match(); ) return 0; ) Sustav: : Tekst : : Redovno. Izrazi
Omogućavanje radnji i pronalaženje pogrešaka Ograničenje broja značajnih znamenki u broju: (s + e)(pd+ + d+(pd* + e)) s = +|p = . d = d s + e = s? = (+|-)? pd* + e = (pd*)? = (.d*)? @"(+|-)? (. d+|d+(. d*)?)" ili @"^(+|-)? (. d+|d+(. d*)?)$" Regularni izraz r = novi regularni izraz (@"^(+|-)? (. (? "cifra"d)+|(? "cifra"d)+(. (? "cifra"d)*)?)$"); Spajanje m = r. Podudaranje ("+1. 23456789"); if (m. Uspjeh) ( Grupa g = m. Grupe ["cifra"]; if (g. Hvata. Broj
Omogućavanje radnji i pronalaženje pogrešaka Određivanje položaja pogreške: Regex r = new Regex(@"(+|-)? (. (? "digit"d)+|(? "digit"d)+(. (? "digit" d )*)?)"); string str = "+1. 2345!678"; Spajanje m = r. Podudaranje(str); if (m. Uspjeh) ( Grupa g = m. Grupe["digit"]; if (g. Hvata. Broji 0) Konzola. Zapiši. Redak("Pogreška na poziciji 1: neočekivani znak "(0)"", str ); inače ako (m. Duljina
Omogućavanje radnji i traženje pogrešaka Određivanje pozicije pogreške: 1. prva pozicija lanca unosa (1), ako prvo podudaranje ne počinje s pozicije Index = 0; 2. pozicija koja slijedi nakon posljednjeg podudaranja (podudaranje. Dužina + 1), ako ne odgovara zadnjoj poziciji ulaznog lanca; 3. položaj prvog razmaka između podudaranja (match[i]. Index + match[i]. Length + 1), ako znak koji slijedi nakon prethodnog podudaranja nije prvi znak sljedećeg podudaranja.
Index) break; indeks = m[i]. Indeks + m[i]. Duljina; ) Konzola. Pisati. Linija("Pogreška na poziciji (0) "(1)"", indeks + 1, str); ) "abc. xyz. pqr" – točno; "+abc. xyz. pqr” – greška u poziciji 1 (“+”); "abc. xyz. pqr! – greška u poziciji 12 (“!”); "abc. xyz!. pqr" – greška na poziciji 8 (“!").
Omogućavanje radnji i traženje pogrešaka Ali! "abc. xyz. +pqr” – greška na poziciji 8 (“.”). Nova opcija predloška: @"w+(. w+)*(. (? !$))? " Validacija: "abc. xyz. +pqr” – greška u poziciji 9 (“+”); "abc. xyz. pqr. " – greška u poziciji 12 (".").
Uravnotežene definicije: "(? "x")" dodaje jedan element u kolekciju pod nazivom "x"; “(? “-x”)” uklanja jedan element iz kolekcije “x”; "(? (x)(? !))" provjerava da nema preostalih elemenata u kolekciji "x". L jezik koji opisuje Pascal ugniježđene operatore “početak kraj; ": @"^s*((? "počinje+)+(? "-početak"završava*; s*)+)*(? (početak)(? !))$".
Pogodnije je opisati vokabular jezika u obliku regularnih izraza i prepoznati jezik pomoću CA. Stoga je važno moći pretvoriti jezične definicije u obliku regularnih izraza u definiciju u obliku CA. Ovu transformaciju predložio je Kenneth Thompson.
Konačni automat je pet (S, S, d, S 0 , F)
S je konačan skup stanja.
S je konačan skup valjanih ulaznih signala.
d - prijelazna funkcija. On reflektira skup Sx(SÈ(e)) u skup stanja nedeterminističkog konačnog automata. Za deterministički automat, prijelazna funkcija reflektira skup SxS u skup stanja automata. Drugim riječima, ovisno o stanju i ulaznom simbolu, d određuje novo stanje stroja.
S 0 - početno stanje konačnog automata, S 0 O S.
F je skup konačnih stanja automata, F O S.
Rad konačnog stroja je niz koraka. Korak je određen stanjem stroja i simbolom unosa. Sam korak se sastoji od promjene stanja stroja i čitanja sljedećeg simbola ulazne sekvence.
Postoje sljedeća pravila za pretvaranje regularnih izraza u stroj stanja.
1 Regularni izraz “e” transformira se u automat dvaju stanja i e-prijelaza između njih (slika 1).
Slika 1. – Automatski stroj za e-prijelaz
2 Regularni izraz od jednog znaka “a” pretvara se u konačni automat dvaju stanja i prijelaza između njih na temelju ulaznog signala a (slika 2).
Slika 2. – Automatski stroj za kretanje simbolom a
3 Neka postoji regularni izraz rs i konačni automati za izraze r i izraze s već su izgrađeni. Zatim su dva stroja povezana u seriju. Slika 3 prikazuje originalne automate za jezike r i s. Na slici je prikazan automat za prepoznavanje ulančanosti ovih jezika.
Stroj za r Stroj za s
Slika 3. – Inicijalni automati
Slika 4. – Stroj za ulančavanje jezika
4 Neka postoji regularni izraz r | s i konačni automati već su izgrađeni za izraz r i izraz s (slika 3). Tada rezultirajući automat mora imati alternativu za izvršavanje jednog od dva automata. Odnosno, automat za izraz r | s za automate za r i s sa slike 3 ima oblik prikazan na slici 5.
Slika 5. – Automatski stroj za kombiniranje jezika
5 Neka postoji regularni izraz r* za konstruirani konačni automat r. U ovom slučaju, uvode se dva nova stanja kako bi se omogućilo zaobilaženje izraznog automata r, a također se uvodi e-prijelaz između konačnog i početnog stanja kako bi se omogućilo ponavljanje automata r više puta. Ako se za regularni izraz r konstruira automat sličan slici 3, tada regularni izraz r* odgovara konačnom automatu prikazanom na slici 6.
postavke
Prema Kleeneovom teoremu svaki regularni izraz možete pridružiti konačni stroj, koji je formalni model algoritma za prepoznavanje leksema označenih zadanim regularnim izrazom. U najopćenitijim crtama, državni stroj-prepoznavač je određen konačnim skupom karakterističnih stanja ulaznog toka i prijelaza između njih. Promjena stanja događa se kada se simboli ulaznog toka prime iz dane abecede u skladu s prijelaznom funkcijom, koji određuje moguća sljedeća stanja na temelju ulaznog simbola i trenutnog stanja. Među mogućim stanjima ističe se početno(početno) i konačni(dopuštajući) stanja u kojima prepoznavač konačnog automata može biti, redom, na početku i završetku obrade tokena ulaznog toka. Ako ulazni niz simbola može generirati niz prijelaza koji mogu prevesti konačni automat iz početnog stanja u jedno od konačnih stanja, tada se smatra prihvatljivim i pripada regularnom skupu koji prepoznaje.
(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*
stol 1
| 0 | 1 | |
| P1 | Q4 | Q2 |
| Q2 | Q3 | P1 |
| Q3 | Q2 | Q4 |
| Q4 | P1 | Q3 |
Stupci prijelazne tablice označavaju znakove ulazne abecede, a redovi odgovaraju trenutnim stanjima DFA. Elementi svakog retka označavaju stanja DFA, u koje mora prijeći iz trenutnog stanja nakon primanja odgovarajućih znakova ulazne abecede. Konkretno, iz prvog retka ove prijelazne tablice slijedi da primanje simbola 0 i 1 u početnom stanju Q1 prevodi DFA u stanja Q4 odnosno Q2.
Prilikom prepoznavanja ulazne sekvence pomoću prijelazne tablice, lako je pratiti promjene u stanju DFA kako bi se utvrdilo je li jedno od dopuštajućih stanja postignuto ili ne. Konkretno, za binarni vektor 01001000 s parnim brojem nula i jedinica, razmatrani DFA generira sljedeći niz prijelaza, gdje je svaki prijelaz označen simbolom ulazne abecede koja ga uzrokuje:
Q1 0 Q4 1 Q3 0 Q2 0 Q3 1 Q4 1 Q1 0 Q4 0 Q1
Ova sekvenca prijelaza završava s dopuštenim stanjem Q1, stoga binarni vektor 01001000 pripada regularnom skupu koji prepoznaje razmatrani DFA i zadovoljava gornji regularni izraz.
Zaključno treba napomenuti da je razmatrani neformalni način gradnje
Za daljnje proučavanje svojstava konačnih automata, a posebno za rješavanje problema sinteze, važan je sljedeći teorem.
Teorem 7.7 (teorem o determinizaciji). Za svaki konačni automat može se konstruirati ekvivalentan deterministički konačni automat.
Da bi se dokazao teorem, potrebno je, prvo, opisati algoritam za konstruiranje determinističkog konačnog automata iz originalnog; drugo, opravdati ovaj algoritam rigoroznim dokazivanjem da on doista proizvodi stroj stanja koji je deterministički i ekvivalentan originalnom. Ovdje prikazujemo samo algoritam za konstruiranje determinističkog automata.
Transformacija proizvoljnog konačnog automata u ekvivalentni deterministički se provodi u dvije faze: prvo se uklanjaju lukovi s oznakom \lambda, zatim se provodi sama determinizacija.
1. Uklanjanje λ-prijelaza (lukovi označeni \lambda).
Za prelazak s izvornog konačnog automata M=(V,Q,q_0,F,\delta) na ekvivalentni konačni automat M"=(V,Q",q_0,F",\delta") bez λ-prijelaza, dovoljno je u originalu napraviti sljedeće transformacije u grafu M.
A. Brišu se sva stanja osim početnog u koje ulaze samo lukovi s oznakom \lambda; čime se definira skup Q" konačnog automata M". Jasno je da Q"\subseteq Q. Pritom pretpostavljamo da početno stanje ostaje isto.
b. Skup lukova konačnog automata M" i njihovih oznaka (a time i prijelazne funkcije M" ) definiran je na sljedeći način: za bilo koja dva stanja p,r\in Q",~ p\to_(a)r se pojavljuje ako i samo ako je \in V , au grafu M vrijedi jedna od dvije stvari: ili postoji luk od p do r čija oznaka sadrži simbol a, ili postoji stanje q takvo da je p\Rightarrow_(\lambda)^( +)q i q\ to_(a)r U ovom slučaju, vrh q, općenito govoreći, ne mora pripadati skupu Q", tj. može nestati kada prijeđe na automat M" (sl. 7.11). Ako je q\in Q" , tada će, naravno, luk (q,r) biti sačuvan u M" i simbol a će biti jedan od simbola koji pripadaju oznaci ovog luka (sl. 7.12).
Dakle, u M" su pohranjeni svi lukovi M čije su oznake različite od \lambda i koji povezuju par (vrhova) stanja iz skupa Q" (nije izbrisan prema dijelu a). Osim toga, za bilo koju trojku stanja p,q,r (ne nužno različita!), takva da je p,r\in Q" i postoji put duljine različite od nule od p do q, čija je oznaka jednaka do \lambda (tj. put pomoću λ-prijelaza), a luk vodi od q do r, čija oznaka sadrži simbol a ulazne abecede, u M" je konstruiran luk od p do r, oznaka od koji sadrži simbol a (vidi sl. 7.11).
V. Skup konačnih stanja F" konačnog automata M" sadrži sva stanja q\u Q", tj. stanja konačnog automata M koja nisu izbrisana prema paragrafu a, za koja q\Rightarrow_(\lambda)^(\ ast) drži q_f za neki q_f\in F (tj. ili je samo stanje q konačno stanje konačnog automata M, ili put duljine različite od nule vodi od njega duž lukova označenih \lambda do jednog od konačnih stanja konačni automat M) (sl. 7.13) .
2. Sama determinacija.
Neka je M=(Q,V,q_0,F,\delta) konačan automat bez λ-prijelaza. Konstruirajmo deterministički konačni automat M_1 ekvivalentan M.
Ovaj konačni automat je definiran na način da je njegov skup stanja skup svih podskupova skupa stanja konačnog automata M. To znači da je svako pojedinačno stanje konačnog automata M_1 definirano kao određeni podskup skupa stanja konačnog automata M. U ovom slučaju, početno stanje novog konačnog automata (tj. M_1) je pojedinačni podskup koji sadrži početno stanje starog konačnog automata (tj. M), a završna stanja novog konačnog automata su svi takvi podskupovi Q koji sadrže barem jedan finalni vrh izvornog konačnog automata M.
Ubuduće, dopuštajući određenu slobodu govora, ponekad ćemo stanja konačnog automata M_1 zvati skupovi stanja. Međutim, važno je jasno razumjeti da je svaki takav skup stanja zasebno stanje novog konačnog automata, ali ne skup njegovih stanja. Istovremeno, za izvorni ("stari") konačni automat M to je upravo skup njegovih stanja. Slikovito rečeno, svaki podskup stanja starog konačnog automata je "srušen" u jedno stanje novog konačnog automata*.
*Formalno, trebali bismo definirati skup Q_1 kao skup koji je u korespondenciji jedan-na-jedan sa skupom 2^Q, ali ipak nam je prikladnije pretpostaviti da se Q_1 podudara s 2^Q - uostalom, skup stanja konačnog automata može biti bilo koji neprazan konačni skup.
Prijelazna funkcija novog konačnog automata definirana je tako da iz skupa stanja S pomoću ulaznog simbola a konačni automat M_1 prelazi u skup stanja, koji je unija svih skupova stanja starog konačnog automata u koji ovaj stari konačni automat koristi simbol a iz svakog skupa stanja S. Dakle, konačni automat M_1 je deterministički po konstrukciji.
Gornji verbalni opis može se prevesti u formule na sljedeći način: gradimo konačni stroj M_1 tako da
M_1=(Q_1,V,\(q_0\),F_1,\delta_1) , gdje
\begin(cases)Q_1=2^Q,\quad F_1=\(T\dvotočka\, T\cap F\ne\varnothing,~T\in2^Q\),\\ (\forall S\subseteq Q) (\zasve a\u V)\Bigl(\delta_1(S,a)= \bigcup\limits_(q\u S)\delta(q,a)\Bigr). \kraj(slučajevi)
Obratimo pozornost na činjenicu da među stanjima novog konačnog automata postoji stanje \varnothing , a prema (7.8), \delta_1(\varnothing,a)=\varnothing za bilo koji ulazni simbol a . To znači da, jednom u takvom stanju, stanje stroja M_1 ga neće napustiti. Općenito, svako stanje q konačnog automata takvo da za bilo koji ulazni simbol a imamo \delta(q,a)=q naziva se apsorbirajućim stanjem konačnog automata. Dakle, stanje \varnothing determinističkog konačnog stroja M_1 je apsorbirajuće. Također je korisno primijetiti da \delta_1(S,a)=\varništa ako i samo ako za svako q\in S (stanja starog konačnog automata iz skupa stanja S ) \delta(q,a)= \varnothing , tj. na grafu M niti jedan luk ne izlazi iz svakog takvog stanja q, označenog simbolom a.
Može se dokazati da je konačni automat dobiven takvim algoritmom ekvivalentan izvornom.
Primjer 7.9. Odredimo konačni automat prikazan na sl. 7.14.
Ekvivalentni konačni automat bez λ-prijelaza prikazan je na slici. 7.15. Imajte na umu da vrh q_2 nestaje, jer u njega ulaze samo "prazni" lukovi.
Da bi se odredio rezultirajući automat, uopće nije potrebno zapisati svih njegovih 2^3=8 stanja, od kojih mnoga možda neće biti dostupna iz početnog stanja \(q_0\) . Za dobivanje stanja koja su dohvatljiva iz \(q_0\), i samo ona, koristit ćemo tzv. pulling metodu.
Ova se metoda općenito može opisati na sljedeći način.
U početnom konačnom automatu (bez praznih lukova) definiramo sve skupove stanja koji su dohvatljivi iz početnog, tj. za svaki ulazni simbol a nalazimo skup \delta(q_0,a) . Svaki takav skup u novom automatu je stanje izravno dostupno iz početnog.
Za svaki od definiranih skupova stanja S i svaki ulazni simbol a nalazimo skup \textstyle(\mathop(\bigcup\limits_(q\in S) \delta(q,a))\limits^(\phantom( A)^( .))) . Sva stanja dobivena u ovom koraku bit će stanja novog (determinističkog) automata, dohvatljivog iz početnog vrha na stazi duljine 2. Opisani postupak ponavljamo sve dok se ne pojave nova skupna stanja (uključujući i prazno!). Može se pokazati da ovo proizvodi sva stanja konačnog automata M_1 koja su dostupna iz početnog stanja \(q_0\) .
Za konačni automat na Sl. 7.15 imamo:
\begin(aligned)& \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)\čaša \delta(q_3,a)= \(q_1\)\šalica\(q_1\)=\(q_1\);\\ & \delta_1(\(q_1, q_3\),b)= \delta(q_1,b)\šalica \delta(q_3,b)= \(q_1\)\šalica\(q_1\)=\(q_1\). \kraj(poravnano)
Budući da se nisu pojavili novi skupovi stanja, postupak "povlačenja" ovdje završava i dobivamo graf prikazan na sl. 7.16.
Redovno dodavanje jezikaJedna od važnih teorijskih posljedica teorema o determinizaciji je sljedeći teorem.
Teorem 7.8. Dopuna redovnog jezika je regularni jezik.
Neka je L pravilan jezik u abecedi V. Tada je komplement jezika L (kao skupa riječi) jezik \overline(L)=V^(\ast)\setminus L .
Prema teoremu 7.7, za regularni jezik L može se konstruirati deterministički konačni automat M koji dopušta L. Budući da je u determinističkom automatu iz svakog vrha za svaki ulazni simbol definiran prijelaz u točno jedan vrh, tada koji god lanac x bio u abecedi V, postoji jedinstvena staza za njega u M, počevši od početnog stanja na kojem je čita se lanac x. Jasno je da je lanac x dopušten automatom M , to jest x\in L(M) , ako i samo ako je posljednje stanje navedenog puta konačno. Slijedi da lanac x\notin L(M) ako i samo ako posljednje stanje navedenog puta nije konačno. Ali trebamo samo konačni automat M" koji dopušta lanac x ako i samo ako ga ne dopušta izvorni konačni automat M. Posljedično, pretvarajući svako konačno stanje od M u ne-konačno stanje i obrnuto, dobivamo deterministički automat koji dopušta dodavanje jezika L .
Dokazani teorem nam omogućuje da izgradimo konačni automat koji ne dopušta određeni skup lanaca, koristeći sljedeću metodu: prvo gradimo automat koji dopušta zadani skup lanaca, zatim ga determiniramo i idemo do automata za zbrajanje kao navedeno u dokazu teorema 7.8.
Primjer 7.10. A. Izgradimo konačni automat koji prihvaća sve lance u abecedi \(0;1\) osim lanca 101.
Prvo, izgradimo konačni automat koji dopušta jedan lanac 101. Ovaj automat je prikazan na Sl. 7.17.
Ovaj automat je kvazi-deterministički, ali nije deterministički, budući da nije u potpunosti definiran. Odredimo ga i dobijemo deterministički ekvivalentni konačni automat prikazan na sl. 7.18.
I konačno, prelazeći na zbrajanje (i preimenovanje stanja), dobivamo automat prikazan na sl. 7.19.
Imajte na umu da su u rezultirajućem automatu svi vrhovi, osim vrha s_3, konačni.
Primijetimo također da se prijelaz na komplement, o kojem se govori u dokazu teorema 7.8, može izvesti samo u determinističkom automatu. Ako bismo zamijenili uloge konačnih i ne-finalnih vrhova u automatu prikazanom na sl. 7.17, tada bismo dobili automat koji dopušta jezik \(\lambda,1,10\) , koji nije - kao što se lako može zamisliti - skup svih lanaca osim lanca 101.
Primijetite također da je konačni stroj na Sl. 7.19 dopušta sve nizove koji sadrže pojavu niza 101, ali ne odgovaraju samom nizu. Ovdje je, na primjer, lanac koji nosi stazu 1011: s_0,s_1,s_2,s_3,t.
b. Izgradimo konačni automat koji prihvaća sve lance u abecedi \(0;1\) osim onih koji sadrže pojavu lanca 101. Razmotrimo jezik L, čiji svaki lanac sadrži pojavu lanca 101. Može se definiran na sljedeći način:
L=(0+1)^(\ast)101(0+1)^(\ast).
Moramo izgraditi automat koji će nadopuniti jezik L.
U ovom slučaju, koristeći se regularnim izrazom izravno, lako je konstruirati konačni automat koji prihvaća jezik L (slika 7.20).
Zatim ćemo provesti determinizaciju metodom “povlačenja”. Rezultat određivanja prikazan je na sl. 7.21.
Za potpuno rješavanje problema ostaje samo na Sl. 7.21 zamijeniti uloge završnih i nefinalnih vrhova (slika 7.22).
V. Raspravljajmo o ideji konstruiranja konačnog automata koji dopušta one i samo one lance u abecedi \(0;1\) koji ne počinju s lancem 01 i ne završavaju s lancem 11 (tj. lanci oblik 01x i lanci tipa y11 nisu dopušteni, bez obzira kakvi bili lanci x,y\in\(0;1\) ).
U ovom slučaju, komplement jezika za koji je potrebno konstruirati konačni automat je skup svih takvih lanaca nula i jedinica koji počinju s lancem 01 ili završavaju s lancem 11. Automat koji dopušta ovaj skup lanci je konstruiran kao automat za kombiniranje 01(0+1)^(\ ast)+(0+1)^(\ast)11 na isti način kao što je opisano u dokazu Kleeneova teorema (vidi teorem 7.6).
Iz svojstva da je klasa regularnih jezika zatvorena u odnosu na komplement (vidi teorem 7.8) odmah slijedi da je ova klasa zatvorena u odnosu na presjek, teoriju skupova i simetričnu razliku.
Korolar 7.3. Za bilo koja dva regularna jezika L_1 i L_2 sljedeće su izjave istinite:
1) sjecište L_1\cap L_2 je pravilno;
2) razlika L_1\setminus L_2 je regularna;
3) simetrična razlika L_1\vartrokut L_2 je pravilna.
Valjanost izjava proizlazi iz identiteta:
\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\,\trokut\ ,L_2 = (L_1\šalica L_2)\setminus (L_1\kapa L_2).\kraj(poravnano)
Prvo, dobiveni rezultati omogućuju nam da tvrdimo da je klasa regularnih jezika s obzirom na operacije unije, presjeka i zbrajanja Booleova algebra, u kojoj je jedinica univerzalni jezik, a nula prazan jezik. Drugo, ova algebarska svojstva obitelji regularnih jezika omogućuju nam da riješimo važan problem prepoznavanja ekvivalencije dva proizvoljna konačna automata.
Prema definiciji 7.10, konačni automati su ekvivalentni ako su jezici koje prihvaćaju isti. Stoga je za provjeru ekvivalentnosti automata M_1 i M_2 dovoljno dokazati da je simetrična razlika jezika L(M_1) i L(M_2) prazna. Da bismo to učinili, dovoljno je konstruirati automat koji dopušta ovu razliku i osigurati da je jezik koji dopušta prazan. Općenito, problem prepoznavanja da je jezik stroja stanja prazan naziva se problem praznine stroja stanja. Za rješavanje ovog problema dovoljno je pronaći skup konačnih stanja automata koji su dostupni iz početnog stanja. Budući da je konačni stroj usmjereni graf, ovaj se problem može riješiti, na primjer, pretraživanjem u širinu. Jezik koji dopušta konačni stroj je prazan ako i samo ako je skup konačnih stanja do kojih se može doći iz početnog stanja prazan. U praksi je poželjno prepoznati ekvivalenciju konačnih automata korištenjem algoritma minimizacije, ali sada nam je važno naglasiti da temeljna mogućnost rješavanja problema ekvivalencije slijedi iz teorema 7.7 i njegovih algebarskih posljedica.
