Končni avtomati regularnih izrazov. Modifikacija regularnega izraza

Osnova. Avtomati za izraze dolžine 1: in so prikazani na naslednji sliki.

Upoštevajte, da vsak od teh treh strojev niz končnih stanj sestoji iz ene države.

Indukcijski korak. Predpostavimo zdaj, da za vsako regularni izraz dolžina<= k построен соответствующий НКА, причем у него единственное заключительное состояние. Рассмотрим произвольное regularni izraz r dolžine k+1 . Odvisno od zadnje operacije ima lahko eno od treh vrst: (r 1 + r 2), (r 1 r 2) ali (r 1) *. Naj in sta NFA, ki prepoznata jezika L r1 oziroma L r2. Brez izgube splošnosti bomo predpostavili, da imajo različna stanja: .

Potem je NKA, katerega diagram je prikazan na sl. 5.2, prepozna jezik.

Ta stroj ima veliko držav, kjer je q 0 novo začetno stanje, q f je novo (enotno!) končno stanje, program pa vključuje programa avtomatov M 1 in M ​​2 ter štiri nove prehodne ukaze: . Očitno jezik, ki ga priznava NFA M, vključuje vse besede iz L (M 1) in iz L (M 2). Po drugi strani pa vsaka beseda prevede q 0 v q f in po prvem koraku gre pot, ki jo vodi, skozi q 0 1 ali q 0 2 . Ker se stanji M 1 in M ​​2 ne sekata, lahko v prvem primeru ta pot pride do q f samo s -prehodom iz q f 1 in nato . Podobno v drugem primeru.

Za izraz je diagram NFA, ki prepozna jezik L r, predstavljen na naslednji sliki.

Ta stroj ima veliko držav , začetno stanje q 0 = q 0 1 , končno stanje q f =q f 2 , program pa vključuje programa avtomatov M 1 in M ​​2 ter en nov ukaz - prehod iz končnega stanja M 1 v začetno stanje M 2, t.j. . Tukaj je tudi očitno, da vsaka pot od q 0 = q 0 1 do q f =q f 2 poteka skozi -prehod od q f 1 do q 0 2. Zato vsaka beseda, ki jo dovoljuje M, predstavlja veriženje neke besede iz L M1) z neko besedo iz L M2) in kakršno koli veriženje takih besed je dovoljeno. Zato NKA M prepozna jezik.

Naj bo r = r 1 * . Diagram NKA, ki prepozna jezik L r =L r1* = L M1 *, je prikazan na sl. 5.3.

Ta stroj ima veliko držav, kjer je q 0 novo začetno stanje, q f novo (edino!) končno stanje, program pa vključuje program avtomata M 1 in štiri nove prehodne ukaze: . Očitno,. Za neprazno besedo w, po definiciji iteracije za nekaj k >= 1 lahko besedo w razdelimo na k podbesed: w=w 1 w 2 ... w k in to je to. Za vsak i= 1,... ,k beseda w i prevede q 0 1 v q f 1 . Potem za besedo w v diagramu M obstaja pot

Zato,. Nasprotno, če neka beseda prevede q 0 v q f, potem ali obstaja ali pa jo vodi pot, ki, potem ko je prešla od q 0 do q 0 1 in nato večkrat prešla pot od q 0 1 do q f 1 in se vrnila iz q f 1 v q 0 1 s -prehodom, končno iz q f 1 s -prehodom se konča v q f . Zato takšna beseda.

Iz izrekov 4.2 in 5.1 neposredno dobimo

Posledica 5.1. Za vsakogar regularni izraz lahko učinkovito zgradimo deterministični končni stroj, ki prepozna jezik, ki ga predstavlja ta izraz.

Ta izjava je en primer sintezni izreki: glede na opis naloge (jezik kot regularni izraz) je program (DFA), ki ga izvaja, učinkovito sestavljen. Velja tudi obratno - teorem analize.

Izrek 5.2. Za vsak determinističen (ali nedeterminističen) končni avtomat je možno konstruirati regularni izraz

, ki predstavlja jezik, ki ga prepozna ta stroj.

Dokaz tega izreka je precej tehničen in presega obseg našega predmeta. Tako lahko sklepamo, da razred končno avtomatskih jezikov sovpada z razredom običajni jeziki . Odslej ga bomo preprosto imenovali.

razred avtomatskih jezikov

Avtomat M r, ki je zgrajen v dokazu izreka 5.1

• Regularni izrazi (RE) so zelo priročna oblika zapisa tako imenovanih regularnih ali avtomatskih jezikov. Zato se RT uporabljajo kot vhodni jezik v številnih sistemih, ki obdelujejo verige. Oglejmo si primere takih sistemov: ukaz grep operacijski sistem Unix ali podobni ukazi za iskanje nizov v spletnih brskalnikih ali sistemih za oblikovanje besedila. V takih sistemih se RF uporabljajo za opis vzorcev, ki jih uporabnik išče v datoteki. Različne iskalniki
• Generatorji leksikalnih analizatorjev. Leksikalni analizatorji so sestavni del prevajalnika; izvorni program razdelijo na logične enote (žetone), ki so lahko sestavljene iz enega ali več znakov in imajo določen pomen. Generator leksikalnega analizatorja prejme formalne opise leksemov, ki so v bistvu RV, in ustvari DFA, ki prepozna, kateri od leksemov se pojavi v njegovem vnosu.
• RV v programskih jezikih.

V tem članku se bomo najprej seznanili s končnimi avtomati in njihovimi tipi (DFA in NFA), nato pa razmislili o primeru konstruiranja minimalnega DFA z uporabo regularnega izraza.

Končni avtomati

Končni avtomat (FA) je pretvornik, ki vam omogoča, da vhod povežete z ustreznim izhodom, ta izhod pa ni odvisen samo od trenutnega vhoda, ampak tudi od tega, kar se je zgodilo prej, od zgodovine delovanja končnega vhoda. državni stroj. Tudi človeško vedenje, pa ne samo umetni sistemi lahko opišemo s CA. Z uporabo CA je mogoče opisati ne samo vedenje umetnih sistemov, ampak celo človeško vedenje. Na primer, vaša reakcija na to, da vaš sosed ponoči posluša glasno glasbo, bo ena po prvem takem dogodku in povsem drugačna po več takšnih dogodkih. Morda obstajajo takšne zgodbe neskončno število, se postavlja vprašanje; Kakšen spomin mora imeti vesoljsko plovilo, da se za vsako predstrukturo obnaša drugače? Jasno je, da ni mogoče shraniti neskončnega števila zakulisnih zgodb. Zato avtomat nekako razdeli vsa možna ozadja v enakovredne razrede. Dve zgodovini sta enakovredni, če imata enak vpliv na vedenje stroja v prihodnosti. Pokliče se tudi razred enakovrednosti, ki mu je avtomat dodelil svojo trenutno zgodovino notranje stanje stroj.

Zdaj pa poglejmo načine, na katere je mogoče določiti CA. Podajo se lahko v obliki grafov ali v obliki kontrolnih tabel. V obliki grafa je CA podana na naslednji način:

• oglišča grafa ustrezajo stanjem vesoljskega plovila.
• usmerjeni robovi ustrezajo prehodnim funkcijam (zraven vsakega takega roba je označen simbol, vzdolž katerega se izvede prehod).
• vozlišče z robom, ki vstopa vanj in ne zapusti več kot enega stanja, ustreza začetnemu stanju.
• končna stanja vesoljskega plovila so označena z debelim obrisom.

V obliki kontrolne tabele, kot je ta:

• stanja vesoljskega plovila se nahajajo v vrsticah tabele.
• znaki prepoznanega jezika so v stolpcih.
• na križišču je označeno stanje, iz katerega je mogoče doseči to stanje za ta simbol.

Spodaj bo predstavljen primer CA v obliki grafa in v obliki kontrolne tabele.

DKA in NKA

Glavna razlika med DKA in NKA je v tem, da je DKA med delovanjem lahko le v enem stanju, NKA pa v več stanjih hkrati. Kot primer NKA delo mi lahko daš idejo Ameriški fizik Hugh Everett iz dejstva, da vsak dogodek razdeli svet na več svetov, v vsakem od katerih se je ta dogodek končal na svoj način. Na primer, v enem svetu je Hitler osvojil 2. svet. vojni, v drugi - Newton se je namesto fizike lotil posla in odkrivanja zakonov klasična mehanika Moral sem ga odložiti za 50 let, da bi lahko naredili kakršne koli zaključke iz delovanja stroja, je treba preučiti vse "svetove". Ko je bila prebrana celotna vhodna veriga, predpostavimo, da NFA sprejme to verigo, če je zaključil operacijo v sprejemljivem stanju v vsaj enem od mnogih "svetov". V skladu s tem avtomat zavrne verigo, če se konča v nedopustnem stanju v vsakem "svetu". DKA sprejme verigo; to je očitno, če se po branju celotne vhodne verige znajde v sprejemljivem stanju.

V večini primerov je veliko lažje zgraditi NKV kot DKA. Toda kljub temu uporaba NKA za modeliranje ni najboljša dobra ideja. Na srečo je za vsak NFA mogoče sestaviti DFA, ki sprejema isti jezik vnosa. V tem članku ne bomo predstavili algoritma za izdelavo DFA z uporabo NFA, ampak bomo razmislili ta algoritem temelji na jasen primer spodaj.

Konstruiranje minimalnega DFA z uporabo regularnega izraza

Za začetek je tukaj sintaksa RT, uporabljena v tem članku:

• veriženje je podano s presledkom ali praznim nizom (na primer: ab)
• združevanje z uporabo simbola "|".
• ponovitev (zapiranje Kleene), z uporabo simbola "*"

Poglejmo primer, kjer je podan regularni izraz:

xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)

Treba je zgraditi minimalni DFA z uporabo regularnega izraza in pokazati prepoznavanje pravilnih in nepravilnih verig.

Za začetek poenostavimo ta RV, z uporabo desnega distribucijskega zakona veriženja glede na unijo, dobimo naslednji RV:

(xy* | ab | (x | a*)) (x | y*)

Sedaj izdelamo avtomat, ki temelji na tem avtodomu:

Po pravilu za pretvorbo veriženja (pravil za pretvorbo PB v KA ne bomo podajali, ker so povsem očitna) dobimo naslednji avtomat:

Po pravilu preoblikovanja sindikatov:

V skladu s pravilom verižne transformacije:

In na koncu uporabimo pravilo transformacije zaprtja in dobimo εNKA:

Znebimo se ε-prehodov ("zvezdica" označuje končna stanja):

V tem NFA sta stanji s3 in s5 enakovredni, saj je δ(s3, x) = δ(s5, x) = s1 in δ(s3, y) = δ(s5, y) = s5, s7. Preimenujte stanja s6 -> s5 in s7 -> s6:

Gradimo DKA v skladu z NKA:

V tem DFA sta stanji p1 in p5 enakovredni, saj
δ(p1, x) = δ(p5, x) = p4 in δ(p1, y) = δ(p5, y) = p5. Preimenuj stanja p6 -> p5 in p7 -> p6:

Ta stroj je minimalen DKA.

Naj bo δ prehodna funkcija, nato pa razširjeno prehodno funkcijo, zgrajeno iz δ, označimo z δ’, ω pa je vhodna veriga.

Recimo, da je vhod veriga ω = aaax, pričakujemo, da bo stroj v enem od sprejemljivih stanj.

δ’(p0, ε) = p0
δ’(p0, a) = δ(δ’(p0, ε), a) = δ(p0, a) = p3
δ’(p0, aa) = δ(δ’(p0, a), a) = δ(p3, a) = p5
δ’(p0, aaa) = δ(δ’(p0, aa), a) = δ(p5, a) = p5
δ’(p0, aaax) = δ(δ’(p0, aaa), a) = δ(p5, a) = p4

p4 - veljavno končno stanje, zato je veriga aaax pravilna za ta stroj.

Zdaj predpostavimo, da je ω = xyyb:

δ’(p0, ε) = p0
δ’(p0, x) = δ(δ’(p0, ε), x) = δ(p0, x) = p1
δ’(p0, xy) = δ(δ’(p0, x), y) = δ(p1, y) = p1
δ’(p0, xyy) = δ(δ’(p0, xy), y) = δ(p1, y) = p1
δ’(p0, xyyb) = δ(δ’(p0, xyy), b) = δ(p1, b) = ∅

Tukaj vidimo, da če damo simbol b na vhod avtomata, ko je ta v stanju p1, bo ta avtomat umrl, zato je veriga xyyb nepravilna.

P. S. Ta članek je obravnaval algoritem za izdelavo DFA z uporabo RT, vendar obstajajo bolj priročni algoritmi, zlasti za programiranje, vendar je to tema za drug članek ...

Za nadaljnji študij lastnosti končnih avtomatov in še posebej za reševanje problema sinteze pomembno ima naslednji izrek.

Izrek 7.7 (determinizacijski izrek). Za vsak končni avtomat je mogoče sestaviti enakovredni deterministični končni avtomat.

Da bi dokazali izrek, je treba najprej opisati algoritem za konstrukcijo determinističnega končnega avtomata iz prvotnega; drugič, utemeljiti ta algoritem s strogim dokazovanjem, da dejansko proizvaja državni stroj, ki je determinističen in enakovreden prvotnemu. Tukaj predstavljamo le algoritem za konstrukcijo determinističnega avtomata.

Transformacija poljubnega končnega avtomata v enakovrednega determinističnega poteka v dveh stopnjah: najprej se odstranijo loki z oznako \lambda, nato se izvede sama determinizacija.

1. Odstranjevanje λ-prehodov (loki z oznako \lambda).

Za prehod iz prvotnega državnega stroja M=(V,Q,q_0,F,\delta) na enakovredni državni stroj M"=(V,Q",q_0,F",\delta") brez λ-prehodov je dovolj, da v izvirnem grafu M izvedemo naslednje transformacije.

A. Brišejo se vsa stanja, razen začetnega, v katerega vstopajo le loki z oznako \lambda; s tem definira množico Q" končnega avtomata M". Jasno je, da Q"\subseteq Q. Hkrati predpostavimo, da začetno stanje ostane enako.

b. Množica lokov končnega avtomata M" in njihovih oznak (torej prehodna funkcija M") je definirana takole: za katerikoli dve stanji p,r\in Q",~ p\to_(a)r velja, če in samo če a\v V in v grafu M velja ena od dveh stvari: ali obstaja lok od p do r, katerega oznaka vsebuje simbol a, ali pa obstaja stanje q, tako da p\desna puščica_(\lambda)^(+)q

in q\to_(a)r. V tem primeru oglišče q, na splošno, morda ne pripada množici Q", to pomeni, da lahko izgine med prehodom na avtomat M" (slika 7.11). Če je q\in Q" , potem bo seveda lok (q,r) ohranjen v M" in simbol a bo eden od simbolov, ki pripada oznaki tega loka (slika 7.12). Tako so v M" shranjeni vsi loki M, katerih oznake so različne od \lambda in ki povezujejo par (točk) stanj iz množice Q" (ni izbrisano glede na del a). Poleg tega za katero koli trojno stanja p,q,r

(ni nujno drugačen!), tako da je p,r\in Q" in obstaja pot neničelne dolžine od p do q, katere oznaka je enaka \lambda (tj. pot vzdolž λ-prehodov), in od q do r vodi lok, katerega oznaka vsebuje simbol a vhodne abecede, v M" je zgrajen lok od p do r, katerega oznaka vsebuje simbol a (glej sliko 7.11). V. Množica končnih stanj F" končnega avtomata M" vsebuje vsa stanja q\in Q", tj. stanja končnega avtomata M, ki niso izbrisana v skladu z odstavkom a, za katera q\desna puščica_(\lambda)^(\ast)q_f

za nekaj q_f\in F (tj. ali je stanje q samo končno stanje končnega avtomata M ali pa pot neničelne dolžine vodi od njega vzdolž lokov z oznako \lambda do enega od končnih stanj končnega avtomata M) (slika 7.13).

2. Odločitev sama. Naj M=(Q,V,q_0,F,\delta)

Ta končni avtomat je definiran tako, da je njegova množica stanj množica vseh podmnožic množice stanj končnega avtomata M. To pomeni, da je vsako posamezno stanje končnega avtomata M_1 definirano kot določena podmnožica množice stanj končnega avtomata M. V tem primeru je začetno stanje novega končnega avtomata (tj. M_1) podmnožica enega elementa, ki vsebuje začetno stanje starega končnega avtomata (tj. M), končna stanja novega končnega avtomata pa so vse take podmnožice Q, ki vsebujejo vsaj eno končno točko prvotnega končnega avtomata M.

Odslej, dopuščamo nekaj svobode govora, bomo stanja končnega avtomata M_1 včasih imenovali nizi stanj. Pomembno pa je jasno razumeti, da je vsak tak niz stanj ločeno stanje novega končnega avtomata, ne pa niz njegovih stanj. Hkrati pa je za prvotni (»stari«) končni avtomat M to natanko množica njegovih stanj. Figurativno povedano, je vsaka podmnožica stanj starega končnega avtomata "sesedena" v eno stanje novega končnega avtomata*.

*Formalno bi morali definirati množico Q_1 kot množico, ki je v korespondenci ena proti ena z množico 2^Q, vendar je za nas še vedno bolj priročno domnevati, da Q_1 sovpada z 2^Q - navsezadnje je množica stanj končnega avtomata je lahko vsaka neprazna končna množica.

Prehodna funkcija novega končnega avtomata je definirana tako, da iz množice stanj S z vhodnim simbolom a preide končni avtomat M_1 v množico stanj, ki je unija vseh množic stanj stare končne avtomat, v katerega ta stari končni avtomat preide s simbolom a iz vsake množice stanj S. Tako je končni avtomat M_1 po konstrukciji determinističen.

Zgoraj navedeno besedni opis lahko prevedemo v formule na naslednji način: zgradimo končni stroj M_1 tako, da

M_1=(Q_1,V,\(q_0\),F_1,\delta_1), Kje

\begin(cases)Q_1=2^Q,\quad F_1=\(T\dvopičje\, T\cap F\ne\varnothing,~T\in2^Q\),\\ (\forall S\subseteq Q) (\za vse a\in V)\Bigl(\delta_1(S,a)= \bigcup\limits_(q\in S)\delta(q,a)\Bigr). \konec(primeri)

Bodimo pozorni na dejstvo, da je med stanji novega končnega avtomata stanje \varnothing in glede na (7.8) \delta_1(\varnothing,a)=\varnothing za kateri koli vhodni znak a. To pomeni, da ko je enkrat v takem stanju, stanje stroj M_1 ne bo zapustil. Na splošno se vsako stanje q končnega avtomata, tako da za vsak vhodni simbol a velja \delta(q,a)=q, imenuje absorpcijsko stanje končnega avtomata. Tako stanje \varnothing determinističnega končnega avtomata M_1 absorbira. Koristno je omeniti tudi to \delta_1(S,a)=\varničče in samo če je za vsako q\in S (stanja starega končnega avtomata iz množice stanj S) \delta(q,a)=\varnič, tj. v grafu M noben lok ne izstopi iz vsakega takega stanja q, označenega s simbolom a.

Lahko se dokaže, da je končni avtomat, dobljen s tem algoritmom, enakovreden originalnemu.

Primer 7.9. Določimo končni avtomat, prikazan na sl. 7.14.

Enakovreden končni avtomat brez λ-prehodov je prikazan na sl. 7.15. Upoštevajte, da oglišče q_2 izgine, saj vanj vstopajo samo "prazni" loki.

Za določitev nastalega avtomata sploh ni potrebno zapisati vseh njegovih 2^3=8 stanj, od katerih mnoga morda niso dosegljiva iz začetno stanje\(q_0\) . Za pridobitev stanj, ki so dosegljiva iz \(q_0\) in samo njih, bomo uporabili tako imenovano metodo vlečenja.

To metodo lahko na splošno opišemo na naslednji način.

V začetnem končnem avtomatu (brez praznih lokov) definiramo vse množice stanj, ki so dosegljive iz začetnega, tj. za vsak vhodni simbol a najdemo množico \delta(q_0,a) . Vsak tak niz v novem avtomatu je stanje, ki je neposredno dostopno iz začetnega.

Za vsako od definiranih množic stanj S in vsak vhodni simbol a najdemo množico \textstyle(\mathop(\bigcup\limits_(q\in S) \delta(q,a))\limits^(\phantom(A)^(.))). Vsa stanja, pridobljena v tem koraku, bodo stanja novega (determinističnega) avtomata, dosegljivega iz začetnega vozlišča po poti dolžine 2. Opisani postopek ponavljamo, dokler se ne pojavi nobeno novo množično stanje (vključno s praznim!). Lahko se pokaže, da to ustvari vsa stanja končnega avtomata M_1, ki so dosegljiva iz začetnega stanja \(q_0\).

Za končni avtomat 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)\cup \delta(q_3,a)= \(q_1\)\cup\(q_1\)=\(q_1\);\\ & \delta_1(\(q_1, q_3\),b)= \delta(q_1,b)\skodelica \delta(q_3,b)= \(q_1\)\skodelica\(q_1\)=\(q_1\). \konec(poravnano)

Ker se niso pojavili novi nizi stanj, se postopek "vlečenja" tukaj konča in dobimo graf, prikazan na sliki 1. 7.16.

Redno dodajanje jezika

Ena od pomembnih teoretičnih posledic determinizacijskega izreka je naslednji izrek.

Izrek 7.8. Dopolnitev običajnega jezika je navadni jezik.

Naj bo L običajni jezik v abecedi V. Potem je komplement jezika L (kot množice besed) jezik \overline(L)=V^(\ast)\setminus L.

V skladu s teoremom 7.7 je za regularni jezik L mogoče konstruirati deterministični končni avtomat M, ki dopušča L. Ker je v determinističnem avtomatu iz vsake vozlišča za vsak vhodni simbol definiran prehod na natanko eno vozlišče, potem ne glede na to, kakšna je veriga x v abecedi V, obstaja edinstvena pot zanjo v M, ki se začne v začetnem stanju, na katerem veriga x se bere. Jasno je, da je veriga x dovoljena z avtomatom M, to je x\in L(M), če in samo če zadnje stanje navedena pot je končna. Iz tega sledi, da veriga x\notin L(M) če in samo če zadnje stanje podane poti ni končno. Potrebujemo pa samo končni avtomat M", ki dopušča verigo x, če in samo če je ne dovoljuje izvirni končni avtomat M. Posledično, s spreminjanjem vsakega končnega stanja M v nekončno stanje in obratno, dobimo deterministični avtomat, ki dopušča dodajanje jezika L .

Dokazani izrek nam omogoča, da zgradimo končni avtomat, ki ne dovoljuje določenega niza verig, naslednjo metodo: najprej zgradimo avtomat, ki priznava dani niz verige, nato jo določimo in gremo k avtomatu za seštevanje, kot je navedeno v dokazu izreka 7.8.

Primer 7.10. A. Zgradimo končni avtomat, ki sprejme vse verige v abecedi \(0;1\), razen verige 101.

Najprej sestavimo končni avtomat, ki omogoča enojno verigo 101. Ta avtomat je prikazan na sl. 7.17.

Ta avtomat je kvazi-determinističen, ni pa determinističen, ker ni popolnoma definiran. Določimo ga in pridobimo deterministični ekvivalentni končni avtomat, prikazan na sliki. 7.18.

In končno, če se premaknemo na seštevanje (in preimenujemo stanja), dobimo avtomat, prikazan na sl. 7.19.

Naj opozorimo, da so v nastalem avtomatu vse točke, razen točke s_3, končne.

Upoštevajte tudi, da je prehod na dodatek, o katerem govorimo o v dokazu izreka 7.8 lahko izvedemo samo v determinističnem avtomatu. Če bi zamenjali vloge končnih in nekončnih vozlišč v avtomatu, prikazanem na sl. 7.17, potem bi dobili avtomat, ki priznava jezik \(\lambda,1,10\) , ki ni - kot si lahko zlahka predstavljamo - množica vseh verig razen verige 101.

Upoštevajte tudi, da končni avtomat na sl. 7.19 dovoljuje vse nize, ki vsebujejo pojavitev niza 101, vendar se ne ujemajo s samim nizom. Tukaj je na primer veriga poti 1011: s_0,s_1,s_2,s_3,t.

b.

Zgradimo končni avtomat, ki sprejme vse verige v abecedi \(0;1\), razen tistih, ki vsebujejo pojavitev niza 101. Razmislite o jeziku L, katerega vsaka veriga vsebuje pojavitev niza 101. Lahko je opredeljeno kot sledi:

L=(0+1)^(\ast)101(0+1)^(\ast).

Zgraditi moramo avtomat, ki bo dopolnjeval jezik L.

V tem primeru je z neposredno uporabo regularnega izraza enostavno sestaviti končni avtomat, ki sprejema jezik L (slika 7.20).

Nato bomo izvedli determinacijo po »pull« metodi. Rezultat določanja je predstavljen na sl. 7.21. Za popolna rešitev

naloge ostanejo samo na sl. 7.21 zamenjajte vlogi končnih in nekončnih vozlišč (slika 7.22).

V. Razpravljajmo o ideji konstruiranja končnega avtomata, ki omogoča tiste in samo tiste verige v abecedi \(0;1\), ki se ne začnejo z verigo 01 in ne končajo z verigo 11 (tj. verige oblika 01x in verige tipa y11 niso dovoljene, ne glede na to, kakšne so bile verige x,y\in\(0;1\) ). V tem primeru je komplement jezika, za katerega je potrebno zgraditi končni avtomat, množica vseh takih verig ničel in enic, ki se začnejo z verigo 01 ali končajo z verigo 11. Avtomat, ki omogoča ta niz ničel verige je zgrajen kot avtomat za združevanje 01(0+1)^(\ast)+(0+1)^(\ast)11

Iz lastnosti, da je razred običajnih jezikov zaprt glede na komplement (glej izrek 7.8), takoj sledi, da je ta razred zaprt glede na presečišče, teoretično množico in simetrično razliko.

Posledica 7.3. Za katera koli dva običajna jezika L_1 in L_2 veljajo naslednje izjave:

1) presečišče L_1\cap L_2 je pravilno;
2) razlika L_1\setminus L_2 je pravilna;
3) simetrična razlika L_1\vtrikotnik L_2 redna.

Veljavnost trditev izhaja iz istovetnosti:

\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\,\trikotnik\ ,L_2 = (L_1\skodelica L_2)\setminus (L_1\kapa L_2).\konec(poravnano)

Prvič, dobljeni rezultati nam omogočajo, da trdimo, da je razred običajnih jezikov glede na operacije združevanja, preseka in seštevanja Boolov algebra, v kateri je enota univerzalni jezik, nič pa je prazen jezik. Drugič, te algebraične lastnosti družine običajnih jezikov vam omogočajo, da rešite pomemben problem prepoznavanje enakovrednosti dveh poljubnih končnih avtomatov.

V skladu z definicijo 7.10 so končni avtomati enakovredni, če so jeziki, ki jih sprejemajo, enaki. Zato je za preverjanje enakovrednosti avtomatov M_1 in M_2 dovolj dokazati, da je simetrična razlika jezikov L(M_1) in L(M_2) prazna. Da bi to naredili, je dovolj, da zgradite avtomat, ki priznava to razliko, in se prepričate, da je jezik, ki ga priznava, prazen. Na splošno se problem prepoznavanja, da je jezik državnega stroja prazen, imenuje problem praznine državnega stroja. Za rešitev tega problema je dovolj, da najdemo množico končnih stanj avtomata, ki so dosegljiva iz začetnega stanja. Ker je končni avtomat usmerjeni graf, potem je to težavo mogoče rešiti na primer z iskanjem v širino. Jezik, ki ga dovoljuje končni avtomat, je prazen, če in samo če je niz končnih stanj, dosegljivih iz začetnega stanja, prazen. V praksi je zaželeno prepoznati enakovrednost končnih avtomatov z algoritmom za minimizacijo, vendar je zdaj pomembno, da poudarimo, da temeljna možnost rešitve problema enakovrednosti izhaja iz izreka 7.7 in njegovih algebraičnih posledic.

V tem razdelku bomo oblikovali pomembna vprašanja povezanih z običajnimi jeziki. Najprej morate razumeti, kaj pomeni postaviti vprašanje o določenem jeziku. Tipičen jezik je neskončen, zato nima smisla nekomu predstavljati verige tega jezika in postavljati vprašanje, ki zahteva preverjanje neskončno število verige. Veliko bolj smiselno je uporabiti eno od končnih predstavitev jezika, in sicer: DFA, NFA, ε-NFA ali regularni izraz.

Očitno bodo jeziki, predstavljeni na ta način, običajni. V resnici ni mogoče predstaviti povsem poljubnih jezikov. Naslednja poglavja predlagajo končne metode za opisovanje razredov, ki so širši od razreda običajnih jezikov, in iz njih bo mogoče obravnavati vprašanja o jezikih. Vendar pa algoritmi za reševanje številnih vprašanj o jezikih obstajajo samo za razred navadnih jezikov. Ta ista vprašanja postanejo »neodločljiva« (ni algoritmov za odgovore na ta vprašanja), če so zastavljena z uporabo bolj »izrazitih« zapisov (ki se uporabljajo za izražanje večjega števila jezikov) kot predstavitve, razvite za običajne jezike.

Začnimo našo študijo algoritmov za vprašanja o običajnih jezikih z ogledom načinov, na katere se ena predstavitev jezika pretvori v drugo. Še posebej razmislimo o časovni zahtevnosti algoritmov, ki izvajajo transformacije. Nato si bomo ogledali tri osnovna vprašanja o jezikih.

1. Ali je jezik, ki ga opisujemo, prazen niz?

2. Ali nek niz w pripada predstavljenemu jeziku?

3. Sta res dva? različne opise predstavljajo isti jezik? (To vprašanje se pogosto imenuje "enakovrednost" jezikov.)

2.1 Pretvorbe med različnimi jezikovnimi predstavitvami

Vsako od štirih običajnih jezikovnih predstavitev je mogoče pretvoriti v katero koli od ostalih treh. Na sl. 3.1 prikazuje prehode iz ene reprezentacije v drugo. Čeprav obstajajo algoritmi za katero koli od teh transformacij, nas včasih ne zanima samo izvedljivost določene transformacije, ampak tudi čas, potreben za njeno izvedbo. Zlasti je pomembno razlikovati med algoritmi, ki uporabljajo eksponentni čas (čas kot funkcija velikosti vhodnih podatkov) in se zato lahko izvajajo samo za vhodne podatke relativno majhne velikosti, od tistih algoritmov, katerih čas izvajanja je linearen, kvadraten , ali nizka stopnja polinoma kot funkcija velikosti vhodnih podatkov. Slednji algoritmi so "realistični", ker jih je mogoče izvesti za veliko širši razred težavnih primerov. Poglejmo časovno zahtevnost vsake od obravnavanih transformacij.

Pretvorba NKA v DKA

Čas izvedbe za pretvorbo NFA ali ε-NFA v DFA je lahko eksponentna funkcija od količine NKA navaja. Za začetek računanje ε-zaprtja n stanj traja O(n3) časa. Najti je treba vse loke z oznako ε, ki vodijo iz vsakega od n stanj. Če obstaja n stanj, potem je lahko največ n2 lokov. Pametna uporaba sistemskih virov in dobro zasnovane podatkovne strukture zagotavljajo, da je čas za raziskovanje vsakega stanja krajši od O(n2). Pravzaprav lahko za enkratno ovrednotenje celotnega ε-zaprtja uporabimo tranzitivni algoritem zapiranja, kot je Warshallov algoritem5.

Po izračunu ε-zaprtja lahko nadaljujemo s sintezo DFA z uporabo konstrukcije podmnožic. Glavni vpliv na porabo časa ima število DFA stanj, ki je lahko enako 2n. Za vsako stanje je mogoče prehode izračunati v O(n3) času z uporabo ε-zaprtja in prehodne tabele NFA za vsak vhodni simbol. Recimo, da moramo izračunati δ((q1, q2, …, qk), a) za DFA. Iz vsakega stanja qi lahko dosežemo največ n stanj po poteh, označenih z ε, in vsako od teh stanj ima lahko največ n lokov, označenih z a. Z ustvarjanjem matrike, indeksirane s stanji, lahko izračunamo unijo največ n nizov največ n stanj v času, sorazmernem z n2.

Na ta način lahko za vsako stanje qi izračunamo nabor stanj, ki so dosegljiva iz qi vzdolž poti, označene z a (po možnosti vključno z loki, označenimi z ε). Ker je k ≤ n, obstaja največ n takih stanj qi in za vsako od njih izračun dosegljivih stanj traja O(n2) časa. torej skupni čas računanje dosegljivih stanj je O(n3). Združevanje nizov dosegljivih stanj bo zahtevalo le O(n2) dodatnega časa, zato izračun enega prehoda DFA traja O(n3) časa.

Upoštevajte, da število vhodnih simbolov velja za konstantno in ni odvisno od n. Tako pri tej in drugih ocenah časa delovanja število vhodnih simbolov ni upoštevano. Vpliva le velikost vnosne abecede konstanten koeficient, ki se skriva v označbi “O big”.

Torej je čas za pretvorbo NKA v DKA, vključno s situacijo, ko NKA vsebuje ε-prehode, O(n32n). Seveda je v praksi običajno število konstruiranih stanj veliko manjše od 2n. Včasih jih je samo n. Zato lahko nastavimo oceno časa delovanja na O(n3s), kjer je s število stanj, ki jih DFA dejansko ima.

Pretvorba DKA v NKA

To je preprosta transformacija, ki traja O(n) časa za DFA z n stanji. Vse, kar je treba storiti, je spremeniti prehodno tabelo za DFA tako, da zaprete stanja v oklepaje () in dodate tudi stolpec za ε, če želite dobiti ε-NFA. Ker se predpostavlja, da je število vhodnih simbolov (tj. širina preskočne tabele) konstantno, kopiranje in obdelava tabele traja O(n) časa.

Pretvarjanje avtomata v regularni izraz

V vsaki od n stopenj (kjer je n število stanj DFA) se lahko velikost sestavljenega regularnega izraza štirikrat poveča, saj je vsak izraz sestavljen iz štirih izrazov prejšnjega cikla. Torej preprosto pisanje n3 izrazov lahko traja O(n34n) časa. Izboljšana zasnova iz razdelka 3.2.2 zmanjša konstantni faktor, vendar ne vpliva na eksponentnost tega problema (v najslabšem primeru).

Podobna konstrukcija zahteva enak čas delovanja, če se pretvori NFA ali celo ε-NFA, vendar to tukaj ni dokazano. Vendar pa je uporaba zasnove za satelite velika vrednost. Če najprej pretvorite NFA v DFA in nato DFA v regularni izraz, bo trajalo O(n34n32n) časa, kar je dvojno eksponentno.

Pretvarjanje regularnega izraza v avtomat

Pretvorba regularnega izraza v ε-NFA bo zahtevala linearni čas. Regularni izraz morate učinkovito razčleniti z uporabo metode, ki za regularni izraz dolžine n6 potrebuje O(n) časa. Rezultat je drevo z enim vozliščem za vsak znak regularnega izraza (čeprav oklepaji v tem drevesu niso prikazani, saj nadzirajo samo razčlenjevanje izraza).

Nastalo drevo danega regularnega izraza je mogoče obdelati s konstruiranjem ε-NFA za vsako vozlišče. Pravila preoblikovanja regularnih izrazov, predstavljena v razdelku 3.2.3, nikoli ne dodajo več kot dveh stanj in štirih lokov v vsako vozlišče izraznega drevesa. Posledično sta tako število stanj kot število lokov nastalega ε-NFA enako O(n). Poleg tega je delo pri ustvarjanju teh elementov na vsakem vozlišču razčlenjevalnega drevesa konstantno, pod pogojem, da funkcija, ki obdeluje vsako poddrevo, vrne kazalce na začetna in sprejemna stanja tega avtomata.

Prišli smo do zaključka, da izdelava ε-NFA z uporabo regularnega izraza zahteva čas, linearno odvisen od velikosti izraza. Možno je odpraviti ε-prehode iz ε-NFA z n stanji tako, da ga preoblikujemo v običajni NFA v času O(n3) in brez povečanja števila stanj. Vendar lahko pretvorba v DKA traja eksponentno.

Oglejmo si algoritem za konstruiranje nedeterminističnega končnega avtomata z uporabo regularnega izraza, ki sprejema isti jezik.

Algoritem 3.1. Konstrukcija nedeterminističnega končnega avtomata z uporabo regularnega izraza.

Vhod. Regularni izraz r v abecedi T.

Izhod. NKA M tako, da je L(M) = L(r) .

Metoda.Avtomat za izraz je sestavljen s sestavo avtomatov, ki ustrezajo podizrazom. Na vsakem koraku konstrukcije ima avtomat v izdelavi natanko eno končno stanje; ni prehodov v začetno stanje iz drugih stanj in ni prehodov iz končnega stanja v druga.

Konstrukcija determinističnega končnega avtomata iz nedeterminističnega

Razmislimo o algoritmu za konstruiranje iz nedeterminističnega končnega avtomata determinističnega končnega avtomata, ki sprejema isti jezik.

Algoritem 3.2. Konstrukcija determinističnega končnega avtomata iz nedeterminističnega.

Vhod. NKA M = (Q, T, D, q 0 , F) .

Izhod. DKA.

Metoda. Vsako stanje nastalega DFA je določen nabor stanj izvirnega NFA.

Algoritem bo uporabil naslednje funkcije: - množica stanj NFA, dosegljivih iz stanj, vključenih v R, samo skozi prehode vzdolž e, to je množica

Množica NFA stanj, v katera obstaja prehod na vhodu a za stanja iz R, to je množica

Sprva sta Q" in D" prazna. Sledite korakom 1–4:

(1) Določite .

(2) Dodaj v Q" kot neoznačeno stanje

(3) Izvedite naslednji postopek:

(4) Določite .

Primer 3.6. Rezultat uporabe algoritma 3.2 je prikazan na sl.

riž. 3.10.

Gradnja determinističnega končnega avtomata z uporabo regularnega izraza

Predstavimo zdaj algoritem za konstruiranje determinističnega končnega avtomata z uporabo regularnega izraza, ki sprejema isti jezik [?].

Naj bo v abecedi T podan regularni izraz r. Regularnemu izrazu r dodajte oznako konca: (r)# . Tak regularni izraz bomo imenovali dokončan. Med svojim delovanjem bo algoritem uporabljal zaključen regularni izraz. Algoritem bo deloval na sintaksnem drevesu za razširjeni regularni izraz (r)#, katerega vsak list je označen s simbolom , in vsak notranje vertex

je označen z eno od operacij: (veriženje), |

(unija), * (iteracija).

Vsakemu listu drevesa (razen e-listom) dodelimo edinstveno številko, imenovano pozicija, in jo uporabimo na eni strani za sklicevanje na list v drevesu, na drugi strani pa za sklicevanje na simbol, ki ustreza temu listu. Upoštevajte, da če je znak uporabljen večkrat v regularnem izrazu, ima več položajev.