Epädeterministinen tilakone

Ei-deterministinen äärellinen automaatti (NFA, eng. nondeterministic finite automaton , NFA) on deterministinen äärellinen automaatti (DFA, eng. deterministic finite automaton , DFA), joka ei täytä seuraavia ehtoja:

mikä tahansa sen siirtymä määräytyy yksiselitteisesti nykyisen tilan ja syöttösymbolin perusteella
jokaista tilamuutosta varten tarvitaan syötemerkki.

Erityisesti mikä tahansa DFA on myös NFA.

Alijoukon rakennusalgoritmia käyttämällä mikä tahansa NFA voidaan muuntaa vastaavaksi DFA:ksi, eli DFA:ksi, joka tunnistaa saman muodollisen kielen [1] . Kuten DFA, NFA tunnistaa vain tavalliset kielet .

NFA:ta ehdottivat vuonna 1959 Michael O. Rabin ja Dana Scott [2] , jotka osoittivat sen vastaavan DFA:ta. NFA:ta käytetään säännöllisten lausekkeiden toteutuksessa - Thompsonin konstruktio on algoritmi säännöllisen lausekkeen muuntamiseksi NFA:ksi, joka tunnistaa tehokkaasti merkkijonojen kuvion. Käänteisesti Kleenen algoritmia voidaan käyttää NFA:n muuntamiseen säännölliseksi lausekkeeksi , jonka koko riippuu yleensä eksponentiaalisesti automaatin koosta.

NFA on yleistetty monella tapaa, esimerkiksi: epädeterministiset äärelliset automaatit ε-siirtymillä , äärelliset muuntimet, pushdown- automaatit , vuorottelevat automaatit, ω-automaatit ja todennäköisyysautomaatit . DFA:n lisäksi tunnetaan myös muita NFA:iden erikoistapauksia - yksiselitteiset äärelliset automaatit ( eng. unambiguous finite automata , UFA) ja itsevarmentavat äärelliset automaatit ( eng. self-verifying finite automata , SVFA).

Epävirallinen esittely

On olemassa useita epävirallisia vastaavia kuvauksia:

NFA, kuten DFA , ottaa syötemerkkijonon. Jokaisen syöttösymbolin kohdalla se siirtyy uuteen tilaan, kunnes se on käsitellyt kaikki syötesymbolit. Automaatti valitsee jokaisessa vaiheessa satunnaisesti yhden mahdollisista siirtymistä. Jos on "toivottava hyväksyntä", toisin sanoen jokin valintasarja, joka johtaa lopulliseen tilaan sen jälkeen, kun syötemerkkijono on haettu kokonaan, merkkijono hyväksytään. Jos ei ole sekvenssiä, joka koko syötemerkkijonon [3] prosessoinnin jälkeen saattaa automatin lopulliseen tilaan, syöttömerkkijono hylätään [4] [5] .
Anna NFA:n ottaa jälleen syötemerkkijonon merkki toisensa jälkeen. Jokaisessa vaiheessa, jossa kaksi tai useampi siirtymä osoittautuu kelvolliseksi, automaatti "kloonaa" itsensä tarvittavaan määrään kopioita, joista jokainen tekee eri siirtymiä. Jos siirtoa ei voida tehdä, nykyinen kopio on umpikuja ja kuolee. Jos kaikki merkit noudettuaan syötemerkkijonosta, jokin kopioista menee lopulliseen tilaan, syöttömerkkijono hyväksytään, muuten se hylätään [6] [7] [8] .

Muodollinen määritelmä

Alkeisempi johdatus muodolliseen määritelmään on artikkelissa " Automaattiteoria ".

Automaatti

NFA on muodollisesti edustettuna 5-osaisena , joka koostuu: $(Q,\Sigma ,\Delta ,q_{0},F)$

äärellinen joukko tiloja . $K$
rajallinen joukko syöttösymboleja . $\Sigma$
siirtymätoiminnot : . $\Delta$ $Q\times \Sigma \rightarrow P(Q)$
alkutila . _ $q_{0}\in Q$
lopullisiksi tiloiksi tunnistettavissa olevat tilat . $F$ $F\subseteq Q$

Tässä tarkoittaa joukon astetta . $P(Q)$ $K$

Tunnustettu kieli

Kun NFA on annettu , se tunnistaa kielen, joka merkitään ja määritellään kaikkien merkkijonojen joukoksi automaatin hyväksymien aakkosten yli . $M=(Q,\Sigma ,\Delta ,q_{0},F)$ $L(M)$ $\Sigma$ $M$

Yleisesti ottaen yllä olevien epävirallisten selitysten mukaan on olemassa useita vastaavia automaatin hyväksymiä muodollisia merkkijonomäärityksiä : ${\displaystyle w=a_{1}a_{2}...a_{n))$ $M$

$w$ hyväksytään, jos on olemassa tilojen sarja sellainen , että ${\displaystyle r_{0},r_{1},...,r_{n))$ $K$
1. $r_{0}=q_{0}$
2. $r_{i+1}\in \Delta (r_{i},a_{i+1})$ , varten $i=0,\ldots ,n-1$
3. $r_{n}\in F$ .

Sanat. Ensimmäinen ehto sanoo, että kone alkaa tilasta . Toinen ehto sanoo, että jokaisen merkkijonon merkin kohdalla kone siirtyy tilasta toiseen siirtymäfunktion mukaisesti . Viimeinen ehto sanoo, että kone hyväksyy merkkijonon , jos syötemerkkijono saa koneen päätymään lopulliseen tilaan. Jotta automaatti hyväksyisi merkkijonon , ei edellytetä, että jokin tilasarja päättyy lopulliseen tilaan, riittää, että yksi sarja johtaa sellaiseen tilaan. Muussa tapauksessa, ts ., jos on mahdotonta siirtyä tilasta tilaan , seuraamalla , automaatin sanotaan hylkäävän merkkijonon. Joukko merkkijonoja, jotka automaatti hyväksyy, on automaatin tunnistama kieli , ja tämä kieli on merkitty [9] [10] .

q_{0}

w

\Delta

w

w

w

M

q_{0}

F

w

M

M

L(M)

Vaihtoehtoisesti se hyväksytään, jos , missä on määritelty rekursiivisesti : $w$ $\Delta ^{*}(q_{0},w)\cap F\not =\emptyset$ $\Delta ^{*}:Q\times \Sigma ^{*}\rightarrow P(Q)$
1. ${\displaystyle \Delta ^{*}(r,\epsilon )=\{r\))$ , missä on tyhjä merkkijono $\epsilon$
2. $\Delta ^{*}(r,xa)=\bigcup _{r'\in \Delta ^{*}(r,x)}\Delta (r',a)$ mille tahansa . $x\in \Sigma ^{*},a\in \Sigma$

Toisin sanoen onko kaikkien tilojen joukko saavutettavissa tilasta merkkijonoa hankittaessa . Merkkijono hyväksytään, jos jokin lopputila kohteesta voidaan saavuttaa syötemerkkijonon aloitustilasta [11] [12] .

\Delta ^{*}(r,x)

r

x

w

F

q_{0}

w

Alkutila

Yllä oleva automaattimääritelmä käyttää yhtä alkutilaa , mikä ei ole vaatimus. Joskus NFA määritellään joukolla alkutiloja. On olemassa yksinkertainen rakenne , joka vie NFA:n, jossa on useita alkutiloja, NFA:han, jolla on yksi aloitustila.

Esimerkki

Seuraava binääriaakkosautomaatti määrittää, päättyykö syöttömerkkijono yhteen. Olkoon , jossa siirtymäfunktio voidaan määritellä seuraavalla tilasiirtymätaulukolla (vertaa vasemmalla olevaan yläkuvaan): $M$ $M=(\{p,q\},\{0,1\},\Delta ,p,\{q\})$ $\Delta$

SisäänkäyntiOsavaltio	0	yksi
$s$	${\näyttötyyli \{p\))$	${\näyttötyyli \{p,q\))$
$q$	$\emptyset$	$\emptyset$

Koska joukko sisältää useamman kuin yhden tilan, automaatti on epädeterministinen. Automaattikieli voidaan kuvata säännöllisen lausekkeen antamana säännöllisenä kielenä . $\Delta(p,1)$ $M$ $M$ (0|1)*1

Kaikki mahdolliset tilasekvenssit syötemerkkijonolle "1011" on esitetty alla olevassa kuvassa. Automaatti hyväksyy merkkijonon, koska yksi tilajonoista täyttää yllä olevan määritelmän. Sillä ei ole väliä, että muut jaksot eivät onnistu. Piirustus voidaan tulkita kahdella tavalla: $M$

Yllä olevan "onnen juoksun" selityksen kannalta jokainen kuvion polku edustaa valintojen sarjaa . $M$
Selitettäväksi "kloonauksen" termeillä, jokainen pystysuora sarake näyttää kaikki automaatin kloonit tietyllä hetkellä, useat nuolet, jotka tulevat ulos solmusta, tarkoittavat kloonausta, solmu, jossa ei ole lähteviä nuolia, tarkoittaa kloonin "kuolemaa". $M$

Kyky lukea sama kuvio kahdella tavalla osoittaa myös kahden yllä olevan selityksen vastaavuuden.

Jos tarkastelemme ensimmäistä yllä olevista muodollisista määritelmistä , merkkijono "1011" hyväksytään, koska kun se luetaan , voi käydä läpi tilajono, joka täyttää ehdot 1-3. $M$ $\langle r_{0},r_{1},r_{2},r_{3},r_{4}\rangle =\langle p,p,p,p,q\rangle$
Jos tarkastelemme toista muodollisista määritelmistä, alhaalta ylöspäin oleva kulku osoittaa, että , siis , ja sitten , mistä , ja lopuksi . Koska tämä joukko sisältää , merkkijono "1011" hyväksytään. $\Delta ^{*}(p,\epsilon )=\{p\}$ ${\displaystyle \Delta ^{*}(p,1)=\Delta (p,1)=\{p,q\))$ ${\displaystyle \Delta ^{*}(p,10)=\Delta (p,0)\cup \Delta (q,0)=\{p\}\kuppi \{\))$ ${\displaystyle \Delta ^{*}(p,101)=\Delta (p,1)=\{p,q\))$ ${\displaystyle \Delta ^{*}(p,1011)=\Delta (p,1)\cup \Delta (q,1)=\{p,q\}\kuppi \{\))$ ${\näyttötyyli \{q\))$

Sitä vastoin automaatti hylkää merkkijonon "10" (kaikki mahdolliset tilasarjat tietyn syötteen syötemerkkijonolle näkyvät oikeassa yläkulmassa), koska ei ole polkua, joka saavuttaisi lopullisen tilan lopullisen lukemisen jälkeen. merkki 0. Vaikka tila voidaan saavuttaa ensimmäisen merkin vastaanottamisen jälkeen, "1" ei tarkoita, että syötemerkkijono "10" on hyväksyttävä. Se tarkoittaa vain, että syötemerkkijono "1" olisi hyväksyttävä. $M$ $q$ $q$

DFA-ekvivalenssi

Determinististä äärellistä automaattia ( DFA ) voidaan pitää erikoisena NFA:na, jossa siirtymäfunktiolla on vain yksi aakkosten tila ja kirjain. Näin ollen on selvää, että mikä tahansa muodollinen kieli , joka voidaan tunnistaa DFA:lla, voidaan tunnistaa myös NFA:lla.

Sitä vastoin jokaiselle NFA:lle on DFA, joka tunnistaa saman muodollisen kielen. DFA voidaan rakentaa käyttämällä osajoukkorakennetta .

Tämä tulos osoittaa, että suuresta joustavuudestaan huolimatta NFA ei pysty tunnistamaan kieliä, joita mikään DFA ei voi tunnistaa. Tämä on tärkeää myös käytännössä, jotta rakenteellisesti yksinkertaisemmat NFA:t muunnetaan laskennallisesti tehokkaammiksi DFA:iksi. Jos NFA:ssa on kuitenkin n tilaa, tuloksena olevalla DFA:lla voi olla jopa 2n tilaa, mikä tekee rakentamisesta joskus epäkäytännöllistä suurille NFA:ille.

NCA ε-siirtymillä

Epädeterministinen äärellinen automaatti ε-siirtymällä (NFA-ε) on lisäyleistys jo NFA:lle. Tämän siirtymäfunktioautomaatin syötteenä saa olla tyhjä merkkijono ε. Siirtymää ilman syöttösymbolia kutsutaan ε-siirtymäksi. Tilakaaviossa nämä siirtymät on yleensä merkitty kreikkalaisella kirjaimella ε. ε-siirtymät tarjoavat kätevän tavan mallintaa järjestelmiä, joiden nykyistä tilaa ei tarkasti tunneta. Jos esimerkiksi mallinnetaan järjestelmää, jonka nykyinen tila ei ole selvä (jonkin syötemerkkijonon käsittelyn jälkeen) ja joka voi olla joko q tai q', voimme lisätä ε-siirtymän näiden kahden tilan välille, jolloin automaatti saadaan molempiin tiloihin samaan aikaan.

Muodollinen määritelmä

NFA-ε esitetään muodollisesti 5-numerolla , , joka koostuu: $(Q,\Sigma ,\Delta ,q_{0},F)$

äärellinen joukko tiloja $K$
rajallinen joukko syötettyjä merkkejä , jota kutsutaan aakkosiksi $\Sigma$
siirtymätoiminnot _ $\Delta :Q\times (\Sigma \cup \{\epsilon \})\rightarrow P(Q)$
alkutila (tai aloitustila ). $q_{0}\in Q$
joukko tiloja , joita pidetään kelvollisina (tai lopullisina ) tiloina . $F$ $F\subseteq Q$

Tässä tarkoittaa joukon potenssia ja ε tyhjää merkkijonoa. $P(Q)$ $K$

ε-Tilan tai tilajoukon sulkeminen

Merkitään tilalle tilojen joukko, joka on saavutettavissa seuraavista siirtymäfunktioissa olevista ε-siirtymistä , eli jos on olemassa sellainen tilajono , että : $q\in Q$ $E(q)$ $q$ $\Delta$ $p\in E(q)$ ${\displaystyle q_{1},...,q_{k))$

$q_{1}=q$ ,
$q_{i+1}\in \Delta (q_{i},\epsilon )$ mille tahansa $1\leqslant i<k$
$q_{k}=p$ .

Joukko tunnetaan nimellä ε - tilasulkeminen . $E(q)$ $q$

ε-sulkeminen on myös määritelty tilajoukolle. NK-automaatin tilajoukon ε-sulkeutuminen määritellään tilajoukoksi, joka voidaan saavuttaa joukon alkioista ε-siirtymillä. Muodollisesti, varten $P$ $P$ $P\subseteq QE(P)=\cup _{q\in P}E(q)$

Hyväksyttävät tilat

Antaa olla merkkijono aakkosten päällä . Automaatti hyväksyy merkkijonon , jos siinä on tilasarja , jossa on seuraavat ehdot: ${\displaystyle w=a_{1}a_{2}...a_{n))$ $\Sigma$ $M$ $w$ ${\displaystyle r_{0},r_{1},...,r_{n))$ $K$

$r_{0}\in E(q_{0})$
$r_{i+1}\in E(r')$ , missä tahansa $r'\in \Delta (r_{i},a_{i+1})$ $i=0,...,n-1$
$r_{n}\in F$ .

Sanat. Ensimmäinen ehto sanoo, että kone lähtee tilasta, joka on saavutettavissa tilasta ε-siirtymien kautta. Toinen ehto sanoo, että lukemisen jälkeen kone valitsee siirtymän kohdasta toiseen ja suorittaa sitten minkä tahansa määrän ε-siirtymiä siirron mukaan . Viimeinen ehto sanoo, että kone hyväksyy, jos viimeinen syötemerkki saa koneen siirtymään johonkin hyväksytyistä tiloista. Muuten automaatin sanotaan hylkäävän merkkijonon. Sen hyväksymä merkkijonojoukko on kieli , jonka automaatti tunnistaa , ja tämä kieli on merkitty nimellä .

q_{0}

a_{i}

\Delta

r_{i}

r'

\Delta

r'

r_{i+1}

w

M

M

L(M)

Esimerkki

Olkoon NFA-ε binääriaakkosella, joka määrittää, sisältääkö syötemerkkijono parillisen määrän nollia vai parillisen määrän ykkösiä. Huomaa, että 0 esiintymistä on parillinen luku. $M$

Olkoon muodollisessa merkinnässä , jossa siirtymäsuhde voidaan määritellä sellaisella tilasiirtymätaulukolla : $M=(\{S_{0},S_{1},S_{2},S_{3},S_{4}\},\{0,1\},\Delta ,S_{0} ,\{S_{1},S_{3}\})$ $\Delta$

SisäänkäyntiOsavaltio	0	yksi	ε
S0 _	{}	{}	{ S 1 , S 3 }
S1_ _	{ S2 } _	{ S 1 }	{}
S2_ _	{ S 1 }	{ S2 } _	{}
S3_ _	{ S 3 }	{ S4 } _	{}
S4_ _	{ S4 } _	{ S 3 }	{}

$M$ voidaan ajatella kahden DFA :n liittona , joista toinen on valtioiden ja toinen valtioiden kanssa . Kieli voidaan kuvata säännöllisen lausekkeen (1*(01*01*)*) ∪ (0*(10*10*)*) antamana säännöllisenä kielenä . Määrittelemme ε-siirtymien avulla, mutta voimme määritellä ilman niitä. $\{S_{1},S_{2}\}$ $\{S_{3},S_{4}\}$ $M$ $M$ $M$

NFA:iden vastaavuus

Sen osoittamiseksi, että NFA-e vastaa NFA:ta, huomaa ensin, että NFA on NFA-e:n erikoistapaus, jää osoittaa, että mille tahansa NFA-e:lle on vastaava NFA.

Olkoon NFA-ε. NFA vastaa , missä tahansa ja . $A=(Q,\Sigma ,\Delta ,q_{0},F)$ $A'=(Q,\Sigma ,\Delta ',E(q_{0}),F)$ $A$ $a\in\Sigma$ $q\in Q$ $\Delta '(q,a)=E(\Delta (q,a))$

Silloin NFA-e vastaa NFA:ta. Koska NFA vastaa DFA:ta, NFA-e vastaa myös DFA:ta.

Sulkemisominaisuudet

NFA:n sanotaan olevan suljettu ( binäärisen / unaarisen ) operaation vuoksi. Jos NFA tunnistaa kielet, jotka on saatu soveltamalla tätä toimintoa NFA:n tunnistamiin kieliin. NFA:t on suljettu seuraavien toimintojen osalta.

Yhdistäminen (katso kuva)
Risteys
Yhdistäminen
Lisäys
Kleene suljin

Koska NFA:t vastaavat ε-siirtymän epädeterministisiä äärellisiä automaatteja (NFA-ε), yllä olevat sulkemiset on todistettu käyttämällä NFA-ε:n sulkeutumisominaisuuksia. Yllä olevista sulkemisominaisuuksista seuraa, että NFA:t tunnistavat vain tavalliset kielet .

NFA:t voidaan rakentaa mistä tahansa säännöllisestä lausekkeesta käyttämällä Thompson-algoritmia .

Ominaisuudet

Kone aloittaa tietystä alkutilasta ja lukee sen aakkosten kirjaimista koostuvan merkkijonon . Automaatti käyttää siirtymäfunktiota Δ määrittääkseen seuraavan tilan nykyisestä tilasta ja juuri luetun merkin tai tyhjän merkkijonon. Kuitenkin "NFA:n seuraava tila ei riipu vain nykyisestä syöttösymbolista, vaan myös mielivaltaisesta määrästä myöhempiä syöttötapahtumia. Kun näitä myöhempiä tapahtumia tapahtuu, on mahdotonta määrittää, missä tilassa kone on” [13] . Jos automaatti on lopullisessa tilassa viimeisen luetun merkin jälkeen, NFA:n sanotaan hyväksyvän merkkijonon, muuten sen sanotaan hylkäävän merkkijonon.

Kaikkien NFA:n hyväksymien merkkijonojen joukko on kieli, jonka NFA hyväksyy. Tämä kieli on tavallinen kieli .

Jokaiselle NFA:lle löytyy deterministinen äärellinen automaatti (DFA), joka hyväksyy saman kielen. Siksi olemassa oleva NFA on mahdollista muuntaa DFA:ksi (mahdollisesti) yksinkertaisemman koneen toteuttamiseksi. Tällainen muunnos suoritetaan käyttämällä osajoukkokonstruktiota , mikä voi johtaa tarvittavien tilojen määrän eksponentiaaliseen kasvuun. Muodollinen todiste osajoukon rakenteesta on artikkelissa " Osajoukon rakentaminen ".

Toteutus

NFA voidaan mallintaa jollakin seuraavista tavoista:

Muunna vastaavaksi DFA:ksi. Joissakin tapauksissa tämä voi johtaa osavaltioiden määrän räjähdysmäiseen kasvuun [14] .
Ylläpidämme kaikkia tiloja , joihin NFA voi joutua sanan lukemisen jälkeen. Syöttösymbolia käsiteltäessä on tarpeen yhdistää nykyiseen tilajoukkoon sovelletun siirtymäfunktion tulokset seuraavan joukon saamiseksi. Jos ε-siirtymät ovat sallittuja, tulee ottaa mukaan myös kaikki tällaisten siirtymien kautta saavutettavat tilat (ε-sulkeminen). Jokainen vaihe vaatii korkeintaan laskelmia, joissa s on NFA-tilojen lukumäärä. Automaatti hyväksyy merkkijonon silloin ja vain, jos viimeistä syötemerkkiä käsiteltäessä jokin sen hetkisistä tiloista on lopullinen. Merkkijono, jonka pituus on n , voidaan käsitellä O (ns 2 ) ajassa [15] käyttämällä O ( s ) muistia. $s^{2}$

NCA-sovellukset

NFA ja DFA ovat samanarvoisia siinä mielessä, että jos automaatti tunnistaa kielen NFA:lla, myös DFA tunnistaa sen. Päinvastoin on myös totta. Tällaisen vastaavuuden määrittäminen on tärkeää ja hyödyllistä. Tärkeää, koska NFA:ita voidaan käyttää vähentämään matemaattisen työn monimutkaisuutta, jota tarvitaan algoritmiteorian tärkeiden ominaisuuksien määrittämiseen . Esimerkiksi tavallisten kielten sulkeutuneisuus on paljon helpompi todistaa NFA : lla kuin DFA:lla. Hyödyllinen, koska NFA:n luominen tunnistamaan, että kieli on joskus paljon tärkeämpää kuin DFA:n rakentaminen kyseiselle kielelle.

Katso myös

Deterministinen tilakone
Kaksisuuntainen ei-deterministinen äärellinen kone
Automaattinen lehtimuistilla
Turingin kone

Muistiinpanot

↑ Martin, 2010 , s. 108.
↑ Rabin ja Scott, 1959 , s. 114-125.
↑ Vaalisarja voi johtaa "umpikujaan", jossa mikään siirtymistä ei kelpaa nykyiselle syöttösymbolille, ja tämä tapaus katsotaan epäonnistuneeksi (merkkijono hylätään).
↑ Hopcroft, Ullman, 1979 , s. 19.
↑ Aho, Hopcroft & Ullman 1974 , s. 319.
↑ Hopcroft, Ullman, 1979 , s. 19-20.
↑ Sipser, 1997 , s. 48.
↑ Hopcroft, Motwani, Ullman, 2001 , s. 56.
↑ Aho, Hopcroft & Ullman 1974 , s. 320.
↑ Sipser, 1997 , s. 54.
↑ Hopcroft, Ullman, 1979 , s. 21.
↑ Hopcroft, Motwani, Ullman, 2001 , s. 59.
↑ Äärellisen tilan kone FOLDOC ilmainen online-laskennan sanakirja . Käyttöpäivä: 11. helmikuuta 2020. Arkistoitu alkuperäisestä 4. huhtikuuta 2015. (määrätön)
↑ Chris Calabro. NFA DFA räjäyttää. 27-02-2005 . Haettu 11. helmikuuta 2020. Arkistoitu alkuperäisestä 7. helmikuuta 2013. (määrätön)
↑ Hopcroft, Motwani, Ullman, 2001 , s. 153.

Kirjallisuus

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman. Tietokonealgoritmien suunnittelu ja analyysi . - Reading/MA: Addison-Wesley, 1974. - ISBN 0-201-00029-6 .
- Aho A., Hopcroft J., Ulman J. Laskennallisten algoritmien rakentaminen ja analyysi. - Moskova: Mir, 1979.
John E. Hopcroft, Jeffrey D. Ullman. Automaattiteorian, kielten ja laskennan esittely . - Reading/MA: Addison-Wesley, 1979. - ISBN 0-201-02988-X .
- John Hopcroft , Rajeev Motwani , Jeffrey Ullman . Automaattiteorian, kielten ja laskennan esittely . - 2. - Addison Wesley , 2001. - ISBN 0-201-44124-1 .
- John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Johdatus automaatioteoriaan, kieliin ja laskemiseen. - M . : "Williams" , 2002. - 528 s. - ISBN 0-201-44124-1 .
Michael Sipser. Johdatus laskentateoriaan . - Boston/MA: PWS Publishing Co., 1997. - ISBN 0-534-94728-X .
John Martin. Johdatus kieliin ja laskentateoriaan. - McGraw Hill, 2010. - ISBN 978-0071289429 .
Rabin MO, Scott D. Finite Automata and Their Decision Problems // IBM Journal of Research and Development. - 1959. - huhtikuu ( osa 3 , numero 2 ). - doi : 10.1147/rd.32.0114 .
Allan C., Avgustinov P., Christensen AS, Hendren L., Kuzins S., Lhoták O., de Moor O., Sereni D., Sittampalam G., Tibble J. Jäljityssovituksen lisääminen vapailla muuttujilla AspectJ: hen // In Olioohjelmointia, järjestelmiä, kieliä ja sovelluksia käsittelevän 20. vuotuisen ACM SIGPLAN -konferenssin julkaisut . — San Diego, CA, USA: OOPSLA '05. ACM, New York, NY, 2005. s. 345-364. Arkistoitu 18. syyskuuta 2009 Wayback Machinessa

Muodolliset kielet ja viralliset kieliopit
Yleiset käsitteet	Chomsky-hierarkia Aakkoset Sana
Tyyppi 0	Rajoittamaton kielioppi Turingin kone lueteltu kieli Ratkaiseva kieli
Tyyppi 1	Tilanneherkkä kielioppi Tilannekohtainen kieli Lineaarisesti rajattu automaatti
Tyyppi 2	Kontekstiton kielioppi Epäselvä kielioppi Kontekstiton kieli Työntöautomaatti ( deterministinen ) Kasvu Lemma Ogdenin Lemma Cookin lause
Tyyppi 3	Tavallinen kielioppi tavallinen kieli Tavallinen ilme Tilakone ( deterministinen , ei - deterministinen ) DFA-minimointi NFA:n määrittäminen Myhill-Neroden lause
jäsentäminen	LL analysaattori LR jäsentäjä Rekursiivinen laskeutumismenetelmä Kok-Younger-Kasami-algoritmi