Nem determinisztikus állapotgép

A nem-determinisztikus véges automata (NFA, eng. nondeterministic finite automaton , NFA) egy olyan determinisztikus véges automata (DFA, angol determinisztikus véges automata , DFA), amely nem teljesíti a következő feltételeket:

bármely átmenetét az aktuális állapot és a bemeneti szimbólum egyedileg határozza meg
minden állapotváltozáshoz bemeneti karaktert kell olvasni.

Különösen minden DFA egyben NFA is.

Az részhalmaz-konstrukciós algoritmus segítségével bármely NFA konvertálható ekvivalens DFA-vá, azaz olyan DFA-vá, amely ugyanazt a formális nyelvet ismeri fel [1] . A DFA-hoz hasonlóan az NFA is csak a normál nyelveket ismeri fel .

Az NFA-t 1959-ben javasolta Michael O. Rabin és Dana Scott [2] , akik bebizonyították, hogy egyenértékű a DFA-val. Az NFA-t reguláris kifejezések implementálására használják – a Thompson-konstrukció egy olyan algoritmus, amely egy reguláris kifejezést NFA-vá konvertál, amely képes hatékonyan felismerni a karakterláncok mintáját. Ezzel szemben a Kleene-algoritmus felhasználható egy NFA reguláris kifejezéssé alakítására, amelynek mérete általában exponenciálisan függ az automata méretétől.

Az NFA sokféleképpen általánosítható, például: nem-determinisztikus véges automaták ε-átmenetekkel , véges állapotú átalakítók, lenyomó automaták , váltakozó automaták, ω-automaták és valószínűségi automaták . A DFA-n kívül az NFA-k egyéb speciális esetei is ismertek - egyértelmű véges automaták ( eng. unambiguous finite automata , UFA) és önellenőrző véges automaták ( eng. self-verifying finite automata , SVFA).

Informális bemutatkozás

Számos informális egyenértékű leírás létezik:

Az NFA a DFA -hoz hasonlóan bemeneti karaktersorozatot vesz fel. Minden bemeneti szimbólumnál átvált új állapotba, amíg az összes bemeneti szimbólumot fel nem dolgozta. Az automata minden lépésben véletlenszerűen választ egyet a lehetséges átmenetek közül. Ha van egy "reményteljes átadás", azaz valamilyen választási sorozat, amely a bemeneti karakterlánc teljes lekérése után a végső állapothoz vezet, akkor a karakterlánc elfogadásra kerül. Ha nincs olyan sorozat, amely a teljes bemeneti karakterlánc [3] feldolgozása után az automatát a végső állapotba hozza, akkor a bemeneti sztring elutasításra kerül [4] [5] .
Hagyja, hogy az NFA ismét vegyen bemeneti karaktersorozatot, egyik karaktert a másik után. Minden egyes lépésnél, amikor két vagy több átmenet érvényesnek bizonyul, az automata „klónozza” magát a szükséges számú másolatba, amelyek mindegyike más-más átmenetet hajt végre. Ha nem lehet átmenetet végrehajtani, az aktuális másolat zsákutcába kerül, és elhal. Ha az összes karakter lekérése után a bemeneti karakterláncból valamelyik másolat a végső állapotba kerül, akkor a bemeneti karakterlánc elfogadásra kerül, ellenkező esetben elutasításra kerül [6] [7] [8] .

Formális definíció

A formális definíció elemibb bevezetéséért lásd az " Automata elmélet " című cikket.

Automata

Az NFA formálisan egy 5 sorból áll, amely a következőkből áll: $(Q,\Sigma ,\Delta ,q_{0},F)$

állapotok véges halmaza . $K$
bemeneti szimbólumok véges halmaza . $\Sigma$
átmeneti funkciók : . $\Delta$ $Q\times \Sigma \rightarrow P(Q)$
kezdeti állapot . $q_{0}\in Q$
végső állapotként felismerhető állapothalmazok . $F$ $F\subseteq Q$

Itt a halmaz fokát jelenti . $P(Q)$ $K$

Elismert nyelv

Adott egy NFA , felismer egy nyelvet , amelyet az automata által elfogadott ábécé feletti összes karakterlánc halmazaként jelölnek és definiálnak . $M=(Q,\Sigma ,\Delta ,q_{0},F)$ $L(M)$ $\Sigma$ $M$

Általánosságban elmondható, hogy a fenti informális magyarázatok szerint több egyenértékű formális karakterlánc-definíciót is elfogad az automata : ${\displaystyle w=a_{1}a_{2}...a_{n))$ $M$

$w$ akkor fogadjuk el, ha van olyan állapotsorozat , amelyben ${\displaystyle r_{0},r_{1},...,r_{n))$ $K$
1. $r_{0}=q_{0}$
2. $r_{i+1}\in \Delta (r_{i},a_{i+1})$ , for $i=0,\ldots ,n-1$
3. $r_{n}\in F$ .

Szavak. Az első feltétel azt mondja, hogy a gép az állapotból indul . A második feltétel azt mondja ki, hogy a karakterlánc minden egyes karakterénél a gép állapotról állapotra vált át az átmeneti függvénynek megfelelően . Az utolsó feltétel azt mondja, hogy a gép akkor fogad el egy karakterláncot , ha a bemeneti karakterlánc hatására a gép befejeződik a végső állapotában. Ahhoz, hogy egy karakterláncot elfogadjon egy automata , nem szükséges, hogy bármely állapotsorozat egy végállapotban végződjön, elég, ha egy sorozat ilyen állapotba vezet. Ellenkező esetben, azaz ha nem lehet a -ból állapotba lépni, akkor a következőt követve az automata elutasítja a karakterláncot. Az automata által elfogadott karakterláncok halmaza az automata által felismert nyelv , és ezt a nyelvet [9] [10] -ként jelöljük .

q_{0}

w

\Delta

w

w

w

M

q_{0}

F

w

M

M

L(M)

Alternatív megoldásként elfogadható, ha a , ahol rekurzív módon van meghatározva : $w$ $\Delta ^{*}(q_{0},w)\cap F\not =\emptyset$ $\Delta ^{*}:Q\times \Sigma ^{*}\rightarrow P(Q)$
1. ${\displaystyle \Delta ^{*}(r,\epsilon )=\{r\))$ , hol van az üres karakterlánc $\epsilon$
2. $\Delta ^{*}(r,xa)=\bigcup _{r'\in \Delta ^{*}(r,x)}\Delta (r',a)$ bármely . $x\in \Sigma ^{*},a\in \Sigma$

Más szóval, elérhető-e az összes állapot halmaza abból az állapotból , amikor megkapja a karakterláncot . Egy karakterlánc akkor fogadható el, ha a bemeneti karakterlánc [11] [12] kezdõállapotából elérhetõ valamilyen végállapot .

\Delta ^{*}(r,x)

r

x

w

F

q_{0}

w

Kezdeti állapot

A fenti automatadefiníció egyetlen kezdeti állapotot használ , ami nem követelmény. Néha az NFA-t kezdeti állapotok halmazával határozzák meg. Létezik egy egyszerű konstrukció , amely egy több kezdeti állapotú NFA-t egyetlen kezdeti állapotú NFA-ra visz.

Példa

A következő bináris ábécé automata határozza meg, hogy a bemeneti karakterlánc egyre végződik-e. Legyen , ahol az átmeneti függvény a következő állapotátmeneti táblázattal definiálható (hasonlítsa össze a bal oldali felső ábrával): $M$ $M=(\{p,q\},\{0,1\},\Delta ,p,\{q\})$ $\Delta$

BejáratÁllapot	0	egy
$p$	$\{p\}$	${\displaystyle \{p,q\))$
$q$	$\üres készlet$	$\üres készlet$

Mivel a halmaz egynél több állapotot tartalmaz, az automata nem determinisztikus. Az automata nyelv egy reguláris kifejezéssel adott reguláris nyelvként írható le . $\Delta(p,1)$ $M$ $M$ (0|1)*1

Az alábbi ábra az „1011” bemeneti karakterlánc összes lehetséges állapotsorát mutatja. A karakterláncot az automata elfogadja, mert az egyik állapotsor megfelel a fenti definíciónak. Nem számít, hogy a többi sorozat nem sikerül. A rajz kétféleképpen értelmezhető: $M$

A fenti "szerencsés futás" magyarázatát tekintve az ábrán minden útvonal választási sorozatot jelöl . $M$
A „klónozással” magyarázva, minden függőleges oszlop az automata összes klónját mutatja egy adott időpontban, a csomópontból kijövő több nyíl klónozást jelent, a kimenő nyilak nélküli csomópont pedig a klón „halálát”. $M$

Az a képesség, hogy ugyanazt az ábrát kétféleképpen is leolvashatjuk, a fenti két magyarázat egyenértékűségét is mutatja.

Ha figyelembe vesszük a fenti formális definíciók közül az elsőt, akkor az "1011" karakterláncot elfogadjuk, mert ennek beolvasásakor olyan állapotsorozat mehet át , amely teljesíti az 1-3. $M$ $\langle r_{0},r_{1},r_{2},r_{3},r_{4}\rangle =\langle p,p,p,p,q\rangle$
Ha figyelembe vesszük a formális definíciók közül a másodikat, az alulról felfelé haladó szakasz azt mutatja, hogy tehát , majd , honnan , és végül . Mivel ez a készlet tartalmazza a következőt , az „1011” karakterlánc elfogadott. $\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\}\cup \{\))$ ${\displaystyle \Delta ^{*}(p,101)=\Delta (p,1)=\{p,q\))$ ${\displaystyle \Delta ^{*}(p,1011)=\Delta (p,1)\cup \Delta (q,1)=\{p,q\}\cup \{\))$ $\{q\}$

Ezzel szemben a "10" karakterláncot az automata elutasítja (az adott bemenethez tartozó bemeneti karakterlánc összes lehetséges állapotsora a jobb felső ábrán látható), mivel nincs olyan út, amely a végső állapot beolvasása után érné el a végső állapotot. karakter 0. Bár az állapotot az első karakter beérkezése után lehet elérni, az "1" nem jelenti azt, hogy a "10" bemeneti karakterlánc elfogadható. Ez csak azt jelenti, hogy az "1" bemeneti karakterlánc elfogadható. $M$ $q$ $q$

DFA egyenértékűség

A determinisztikus véges automata ( DFA ) az NFA egy speciális fajtájának tekinthető, amelyben az ábécé bármely állapotához és betűihez az átmeneti függvénynek csak egy eredő állapota van. Így egyértelmű, hogy minden formális nyelv , amely DFA-val felismerhető, felismerhető NFA-val is.

Ezzel szemben minden NFA-hoz létezik egy DFA, amely ugyanazt a formális nyelvet ismeri fel. Egy DFA-t [en] lehet ] részhalmaz konstrukcióval .

Ez az eredmény azt mutatja, hogy az NFA a nagy rugalmassága ellenére nem képes felismerni azokat a nyelveket, amelyeket egyetlen DFA sem ismer fel. Ez a gyakorlatban is fontos annak érdekében, hogy a szerkezetileg egyszerűbb NFA-kat számításilag hatékonyabb DFA-kká alakítsuk. Ha azonban az NFA-nak n állapota van, akkor a kapott DFA-nak akár 2n állapota is lehet, ami néha kivitelezhetetlenné teszi a nagy NFA-k esetében.

NCA ε-átmenetekkel

A nem-determinisztikus véges automata ε-átmenetekkel (NFA-ε) egy további általánosítás már az NFA-ra. Ennek az átmeneti függvényautomatának megengedhető, hogy az üres ε karakterlánc legyen bemenetként. A bemeneti szimbólum használata nélküli átmenetet ε-átmenetnek nevezzük. Az állapotdiagramon ezeket az átmeneteket általában a görög ε betűvel jelölik. Az ε-átmenetek kényelmes módot biztosítanak olyan rendszerek modellezésére, amelyek jelenlegi állapota nem pontosan ismert. Például, ha egy olyan rendszert modellezünk, amelynek aktuális állapota nem tiszta (valamilyen bemeneti karakterlánc feldolgozása után), és lehet q vagy q', akkor hozzáadhatunk egy ε-átmenetet a két állapot között, így az automata mindkét állapotba kerül ugyanakkor.

Formális definíció

Az NFA-ε formálisan egy 5 sorból áll , amely a következőkből áll: $(Q,\Sigma ,\Delta ,q_{0},F)$

állapotok véges halmaza $K$
bemeneti karakterek véges halmaza , az úgynevezett ábécé $\Sigma$
átmeneti funkciók $\Delta :Q\times (\Sigma \cup \{\epsilon \})\rightarrow P(Q)$
kezdeti (vagy indítási ) állapot $q_{0}\in Q$
érvényes (vagy végső ) állapotnak tekintett állapotok halmaza . $F$ $F\subseteq Q$

Itt a halmaz hatványát jelenti , ε pedig az üres karakterláncot. $P(Q)$ $K$

ε-Egy állapot vagy állapothalmaz lezárása

Egy állapothoz jelölje az átmeneti függvényekben a következő ε-átmenetekből elérhető állapotok halmazát , nevezetesen, ha van olyan állapotsorozat, amelyre: $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 )$ bármilyen $1\leqslant i<k$
$q_{k}=p$ .

A halmaz ε - állapotú zárás néven ismert . $E(q)$ $q$

Az ε-zárás is definiálva van az állapotok halmazára. Az NK-automata állapothalmazának, , ε-zárását úgy definiáljuk, mint azon állapotok halmazát, amelyek a halmaz elemeiből ε-átmenetekkel elérhetők. Formálisan azért $P$ $P$ $P\subseteq QE(P)=\cup _{q\in P}E(q)$

Elfogadható állapotok

Legyen egy karakterlánc az ábécé fölött . Az automata akkor fogad el egy karakterláncot , ha van egy állapotsorozat a következő feltételekkel: ${\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')$ , hol bármely $r'\in \Delta (r_{i},a_{i+1})$ $i=0,...,n-1$
$r_{n}\in F$ .

Szavak. Az első feltétel azt mondja, hogy a gép olyan állapotból indul ki, amely az állapotból ε-átmeneteken keresztül elérhető. A második feltétel szerint a gép beolvasása után kiválasztja az átmenetet -ról -ra , majd tetszőleges számú ε-átmenetet hajt végre a -ról -ra való átmenetnek megfelelően . Az utolsó feltétel azt mondja, hogy a gép elfogadja , ha az utolsó bemeneti karakter hatására a gép átáll valamelyik elfogadott állapotba. Ellenkező esetben az automatáról azt mondják, hogy elutasítja a karakterláncot. Az általa elfogadott karakterláncok halmaza az a nyelv , amelyet az automata felismer , és ezt a nyelvet a következővel jelöljük .

q_{0}

a_{i}

\Delta

r_{i}

r'

\Delta

r'

r_{i+1}

w

M

M

L(M)

Példa

Legyen egy NFA-ε bináris ábécével, amely meghatározza, hogy a bemeneti karakterlánc páros számú nullát vagy páros számú egyest tartalmaz-e. Vegye figyelembe, hogy a 0 előfordulás páros szám. $M$

Formális jelölésben legyen , ahol az átmeneti reláció egy ilyen állapotátmeneti táblával definiálható : $M=(\{S_{0},S_{1},S_{2},S_{3},S_{4}\},\{0,1\},\Delta ,S_{0} ,\{S_{1},S_{3}\})$ $\Delta$

BejáratÁllapot	0	egy	ε
S0_ _	{}	{}	{ S 1 , S 3 }
S1_ _	{ S2 } _	{ S 1 }	{}
S2_ _	{ S 1 }	{ S2 } _	{}
S3_ _	{ S 3 }	{ S4 } _	{}
S4_ _	{ S4 } _	{ S 3 }	{}

$M$ felfogható két DFA uniójaként , az egyik az államokkal , a másik pedig az állapotokkal . A nyelv leírható reguláris nyelvként , amelyet a reguláris kifejezés adja meg (1*(01*01*)*) ∪ (0*(10*10*)*). Definiálunk ε-átmenetekkel, de definiálhatunk nélkülük is. $\{S_{1},S_{2}\}$ $\{S_{3},S_{4}\}$ $M$ $M$ $M$

NFA-k egyenértékűsége

Annak bizonyítására, hogy az NFA-ε ekvivalens az NFA-val, először is meg kell jegyezni, hogy az NFA az NFA-ε speciális esete, továbbra is meg kell mutatni, hogy minden NFA-ε esetében létezik egy ekvivalens NFA.

Legyen NFA-ε. Az NFA egyenértékű a következővel: , ahol bármely és . $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))$

Ekkor az NFA-ε egyenértékű az NFA-val. Mivel az NFA egyenértékű a DFA-val, az NFA-ε a DFA-val is egyenértékű.

Bezárás tulajdonságai

Egy NFA-ról azt mondják, hogy egy ( bináris / unáris ) művelet miatt zárva van . Ha az NFA felismeri azokat a nyelveket, amelyeket ennek a műveletnek az NFA által felismert nyelvekre történő alkalmazásával szerez. Az NFA-k a következő műveletek tekintetében zárva vannak.

Egyesítés (lásd a képet)
útkereszteződés
Összefűzés
Kiegészítés
Kleene zárás

Mivel az NFA-k ekvivalensek az ε-átmenet nemdeterminisztikus véges automatákkal (NFA-ε), a fenti lezárásokat az NFA-ε zárási tulajdonságaival bizonyítjuk. A fenti lezárási tulajdonságokból következik, hogy az NFA-k csak a reguláris nyelveket ismerik fel .

Az NFA-k bármilyen reguláris kifejezésből felépíthetők a Thompson algoritmus segítségével .

Tulajdonságok

A gép egy bizonyos kezdeti állapotból indul, és beolvassa az ábécé betűiből álló karakterláncot . Az automata a Δ átmeneti függvényt használja az aktuális állapot és az éppen beolvasott karakter vagy üres karakterlánc következő állapotának meghatározására. Azonban „az NFA következő állapota nemcsak az aktuális bemeneti szimbólumtól függ, hanem tetszőleges számú későbbi bemeneti eseménytől is. Amíg ezek a későbbi események zajlanak, lehetetlen meghatározni, hogy a gép milyen állapotban van” [13] . Ha az automata az utolsó beolvasott karakter után a végső állapotban van, az NFA elfogadja a karakterláncot, ellenkező esetben pedig elutasítja a karakterláncot.

Az NFA által elfogadott összes karakterlánc halmaza az a nyelv, amelyet az NFA elfogad. Ez a nyelv egy szabályos nyelv .

Bármely NFA-hoz találhat egy determinisztikus véges automatát (DFA), amely elfogadja ugyanazt a nyelvet. Ezért lehetőség van egy meglévő NFA-t DFA-vá konvertálni egy (esetleg) egyszerűbb gép megvalósítása érdekében. Az ilyen transzformációt az részhalmaz konstrukcióval hajtjuk végre , ami a szükséges állapotok számának exponenciális növekedéséhez vezethet. Az alhalmaz felépítésének hivatalos bizonyítékát lásd a " Részhalmaz felépítése " cikkben.

Megvalósítás

Az NFA a következő módok egyikével modellezhető:

Konvertálni egyenértékű DFA-ra. Bizonyos esetekben ez az államok számának robbanásszerű növekedéséhez vezethet [14] .
Az összes olyan állapot készletének fenntartása , amelyben az NFA a szó elolvasása után kerülhet. Egy bemeneti szimbólum feldolgozásakor össze kell vonni az aktuális állapothalmazra alkalmazott átmeneti függvény eredményeit, hogy a következő halmazt kapjuk. Ha az ε-átmenetek megengedettek, akkor az ilyen átmeneteken keresztül elérhető összes állapotot is tartalmaznia kell (ε-zárás). Minden lépés legfeljebb számítást igényel, ahol s az NFA-állapotok száma. Az automata akkor és csak akkor fogad el egy karakterláncot, ha az utolsó bemeneti karakter feldolgozásakor valamelyik aktuális állapot végleges. Egy n hosszúságú karakterlánc O (ns 2 ) idő alatt [15] feldolgozható O ( s ) memória használatával . $s^{2}$

NCA alkalmazások

Az NFA és a DFA egyenértékűek abban az értelemben, hogy ha egy nyelvet egy NFA felismer egy automata által, akkor azt a DFA is felismeri. Ennek a fordítottja is igaz. Egy ilyen egyenértékűség megállapítása fontos és hasznos. Fontos, mert az NFA-k segítségével csökkenthető az algoritmuselmélet fontos tulajdonságainak megállapításához szükséges matematikai munka bonyolultsága . Például sokkal könnyebb bizonyítani a reguláris nyelvek zártságát NFA-kkal, mint DFA-kkal. Hasznos, mert az NFA létrehozása annak felismerésére, hogy a nyelv néha sokkal fontosabb, mint az adott nyelv DFA-jának létrehozása.

Lásd még

Determinisztikus állapotgép
Kétirányú, nem determinisztikus véges gép
Automata magazinmemóriával
Turing gép

Jegyzetek

↑ Martin, 2010 , p. 108.
↑ Rabin és Scott, 1959 , p. 114–125.
↑ Egy választási sorozat „zsákutcához” vezethet, amelyben az átmenetek egyike sem érvényes az aktuális bemeneti szimbólumra, és ez az eset kudarcnak minősül (a karakterláncot elutasítják).
↑ Hopcroft, Ullman, 1979 , p. 19.
↑ Aho, Hopcroft és Ullman, 1974 , p. 319.
↑ Hopcroft, Ullman, 1979 , p. 19-20.
↑ Sipser, 1997 , p. 48.
↑ Hopcroft, Motwani, Ullman, 2001 , p. 56.
↑ Aho, Hopcroft és Ullman, 1974 , p. 320.
↑ Sipser, 1997 , p. 54.
↑ Hopcroft, Ullman, 1979 , p. 21.
↑ Hopcroft, Motwani, Ullman, 2001 , p. 59.
↑ Véges állapotú gép FOLDOC ingyenes online számítástechnikai szótár . Hozzáférés dátuma: 2020. február 11. Az eredetiből archiválva : 2015. április 4. (határozatlan)
↑ Chris Calabro. Az NFA a DFA felrobbant. 2005-02-27 . Letöltve: 2020. február 11. Az eredetiből archiválva : 2013. február 7.. (határozatlan)
↑ Hopcroft, Motwani, Ullman, 2001 , p. 153.

Irodalom

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman. A számítógépes algoritmusok tervezése és elemzése . - Reading/MA: Addison-Wesley, 1974. - ISBN 0-201-00029-6 .
- Aho A., Hopcroft J., Ulman J. Számítási algoritmusok felépítése és elemzése. - Moszkva: Mir, 1979.
John E. Hopcroft, Jeffrey D. Ullman. Bevezetés az automataelméletbe, a nyelvekbe és a számításba . - Reading/MA: Addison-Wesley, 1979. - ISBN 0-201-02988-X .
- John Hopcroft , Rajeev Motwani , Jeffrey Ullman . Bevezetés az automataelméletbe, a nyelvekbe és a számításba . - 2. - Addison Wesley , 2001. - ISBN 0-201-44124-1 .
- John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Bevezetés az automataelméletbe, a nyelvekbe és a számításba. - M . : "Williams" , 2002. - 528 p. - ISBN 0-201-44124-1 .
Michael Sipser. Bevezetés a számításelméletbe . - Boston/MA: PWS Publishing Co., 1997. - ISBN 0-534-94728-X .
John Martin. Bevezetés a nyelvekbe és a számításelméletbe. - McGraw Hill, 2010. - ISBN 978-0071289429 .
Rabin MO, Scott D. Finite Automata and Their Decision Problems // IBM Journal of Research and Development. - 1959. - április ( 3. köt. 2. szám ). - 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. Trace matching with free variables to AspectJ // In A 20. éves ACM SIGPLAN konferencia előadásai az objektum-orientált programozásról, rendszerekről, nyelvekről és alkalmazásokról . – San Diego, CA, USA: OOPSLA '05. ACM, New York, NY, 2005. 345-364. Archiválva : 2009. szeptember 18. a Wayback Machine -nél

Formális nyelvek és formális nyelvtanok
Általános fogalmak	Chomsky-hierarchia Ábécé Szó
Típus 0	Korlátlan nyelvtan Turing gép felsorolt nyelv Feloldható nyelv
1. típus	Környezetérzékeny nyelvtan Környezetérzékeny nyelv Lineárisan korlátos automata
2. típus	Kontextus mentes nyelvtan Kétértelmű nyelvtan Kontextus mentes nyelv Lenyomó automata ( determinisztikus ) Növekedési Lemma Ogden Lemma Cook-tétel
3. típus	Szabályos nyelvtan szabályos nyelv Reguláris kifejezés Állapotgép ( determinisztikus , nem determinisztikus ) DFA minimalizálás Az NFA meghatározása Myhill-Nerode tétel
elemzése	LL analizátor LR elemző Rekurzív süllyedés módszere Kok-Younger-Kasami algoritmus