Absztrakt automata

Az elméleti számítógép-tudományban, az automata-elmélet az absztrakt számítógépek elméletével és azok problémáival foglalkozik, illetve megoldást keres azokra (azok matematikai reprezentációival, automatákkal, Turing-gépekkel). Az automata-elmélet közeli kapcsolatban áll a formális nyelvek elméletével, ugyanis a formális nyelvek egyes osztályaihoz különböző, azokat felismerni képes automata osztályok rendelhetők. A formális nyelv a matematika, a logika és a informatika számára egy véges ábécéből generálható, véges hosszúságú szavak (például karakter stringek, jelsorozatok) halmaza, amelyekkel a formális nyelvek elmélete foglalkozik.

Fogalomtár
Nézzünk előbb egy pár definíciót, ami később megkönnyítheti az életünket:
 Betű  Itt tényleg egy betűre lehet gondolni. Persze, csak gondolni, hiszen ennek nem kell tényleg betűnek lennie. Lehet bármilyen szimbólum, amíg az a valami egység és megkülönböztethető a többitől.
 Szó  Betűk egy véges sorozata, amely betűk egymás után írásából, konkatenációjából születhet. Az önmagában álló betűt azonosíthatjuk az egy betűből álló szóval.
 Ábécé  Betűk véges halmaza.
 Nyelv  Szavak halmaza egy adott ábécé felett. (Minden szó az adott ábécé betűiből áll.) Lehet véges, vagy végtelen.
 Konfiguráció  Az állapot, amiben az automata van és a szó, ami még a bemeneten maradt. Egy állapotból a másikba való lépést nevezik még konfigurációátmenetnek is.

Automata

Alapozás
Az automata a matematikai modellje egy véges sok állapotú gépnek. Az automata egy olyan gép, mely a bemenetét végigolvasva végighalad valamiféle állapotokon egy állapotátmeneti függvénynek megfelelően, ami megmondja, hogy az aktuális állapotból a bemenettől függően milyen állapotba kerüljön a gép legközelebb. Az állapotátmeneti függvényt táblázat formájában kényelmesen meg lehet adni. A bemenetet a gép elolvassa betűről betűre, amíg az teljesen el nem fogy. (Gondoljunk egy szalagra, amire egy szó van felírva. A szalag felett az automata olvasófeje mozog, betűnként beolvasva azt.) Amikor a szalag elfogy, azt mondjuk, hogy az automata megáll. Az állapottól függően, amelyben az automata megállt, azt mondjuk, hogy elfogadja, vagy elutasítja az olvasott szót. Ha e végállapot egy elfogadó állapot, akkor a szót elfogadta, ha egy elutasító állapotban állt meg, akkor a szót elutasította a gép. Azon szavak halmazát, melyet az automata elfogad, az automata által elfogadott nyelvnek nevezünk.

Egy kicsit formálisabb leírás
Formálisan az automatát egy rendezett 5-ös írja le: , ahol:
Q az állapotok véges halmaza,
∑ a szimbólumok véges halmaza, mely az automata által elfogadott nyelv ábécéje,
δ az állapotátmeneti függvény:

A függvény kiterjeszthető úgy, hogy ne csak egy betűt, hanem egy egész szót fogadjon:

Ahol ∑* a ∑ lezárása.
S0 a kezdőállapot, amiben az automata áll, mikor még nem olvasott semmit a bemenetéről. (Természetesen S0∈ Q)
F állapotok halmaza (F∈Q), ezeket elfogadó állapotoknak nevezzük.
Ezek után mondhatjuk, hogy  nyelvet az A determinisztikus automata elfogadja (Lásd lejjebb. δ definíciója egy kicsit komplikáltabb nemdeterminisztikus automatákra (NFA), ahol  és

Automaták típusai
Az alábbi automaták léteznek:
Determinisztikus automata  A következő állapotot egyértelműen meghatározza az aktuális állapot és az inputon lévő betű. Minden lehetséges betűre létezik következő állapot.
Nemdeterminisztikus automata  Ilyen automatáknak nem biztos, hogy minden betűre van következő állapotuk, illetve lehet, hogy nem is egy, hanem több következő állapot lehetséges. Az automata elfogad egy szót, ha létezik út S0-ból egy végállapotba úgy, hogy az automata végigolvassa a szót. A szót az automata elutasítja, ha nem tudja, hogyan menjen tovább (nincs ebből a konfigurációból átmenet.)
Nemdeterminisztikus, ε-átmenetes automata  Ennek az automatának vannak olyan ε-nal címkézett átmenetei, ahol anélkül kerülhet új állapotba, hogy továbbolvasná az inputot. (Nem érdekli, mi van az inputján, csak megrázza magát és új állapotba kerül.) Megmutatható, hogy mindig lehet találni determinisztikus automatát, ami ugyan azt a nyelvet fogadja el, mint adott nemdeterminisztikus automata.

Automaták kiterjesztései
A fent leírt automaták által elfogadott nyelvek családja a reguláris nyelvek családja. Más automaták komplikáltabb nyelveket is képesek elfogadni. Ilyen automaták például:
 veremautomaták  Az ilyen gépek hasonlóak a determinisztikus automatákhoz, rendelkeznek viszont memóriával is verem (vermek) formájában. A δ állapotátmeneti függvény a verem tetején lévő szimbólumtól is függeni fog, és azt is meg fogja mondani, hogyan változzon a verem az átmenetkor. Ezek az automaták környezetfüggetlen nyelvek elfogadására képesek.
 Turing-gépek  Ezek a legjelentősebb automaták. Végtelen sok memóriával rendelkeznek szalag(ok) formájában, ami(ke)t fej(ekk)el tudnak írni/olvasni, és bármerre mozogni a szalagon. Turing-géppel bármilyen algoritmus megvalósítható (Church-Turing-tézis). Ők képezik a modern számítógépek elméleti alapjait.
 Véges szalaggal rendelkező Turing-gépek  Itt már nincs végtelen hosszú szalag, a szalag hossza az inputtal összemérhető. Ezek a gépek környezetfüggő nyelveket tudnak elfogadni.

Alapok 
Egy automata minden esetben egy véges állapotú gép modellje. Egy véges állapotú gép, adott bemenet függvényében képes a gép különböző állapotain keresztüli ugrásokkal, különböző állapotokat felvenni (ezeket gyakran táblázatosan adják meg). Egy állapotváltozást meghatározó átmeneti függvény vagy átmeneti tábla elem általában az automata aktuális állapotától, valamint az aktuális szimbólumtól függően megadja, az automata következő állapotát. A bemenetről az olvasás a szimbólumokat egymás után teszi hozzáférhetővé az automata számára, mindaddig, amíg a teljes bemenet feldolgozása meg nem történt (ezt úgy kell elképzelni, mintha a bejövő szimbólumok egy szalagra lennének írva, amelyet egy olvasófej szimbólumonként olvas, és minden olvasás után előbbre lép az olvasófej a szalagon következő szimbólumra). Amint a bemenet elfogyott, az automata megáll. Attól függően, hogy milyen állapotban állt meg az automata, mondhatjuk, hogy az elfogadta illetve visszautasította a bemeneti szimbólumsorozatot. Ha az automata elfogadó állapotban állt meg, akkor elfogadta a bemeneti szót, ellenkező esetben pedig visszautasította azt. Az automata által elfogadott összes szó halmazát gyakran nevezik az automata által elfogadott nyelvnek.

Formális leírás

Definíciók
A következőkben néhány, a későbbiek megértését segítő fogalmat definiálunk:
 Szimbólum  Egy olyan önkényesen meghatározott adat, amelynek valamilyen hatása van az automatára.
 Szó  Szimbólumok konkatenációjával előállított, véges hosszúságú jelsorozat vagy string.
 Ábécé  A szimbólumok véges halmaza.
 Nyelv  Egy adott ábécé elemeiből formált szavak véges vagy végtelen halmaza.
 Automata  formálisan egy  5-ös, ahol:
Q az állapotok véges halmaza.
∑ szimbólumok véges halmaza, amit az automata által elfogadott nyelv ábécéjének nevezünk.
δ az átmeneti függvény, amely a következő formájú

Ez a függvény kiterjeszthető úgy, hogy a nem az ábécé egy szimbólumáról beszélünk, hanem a szimbólumokból alkotott stringekről, de akkor az automata stringekre adott válaszát kell vizsgálni, amelyet a string beolvasása és feldolgozása után ad. A függvény átírható a következő alakba

…ahol ∑* ∑ Kleene lezárása
S0 a kiiduló állapot, azaz, ebben az állapotban van az automata, amíg el nem kezdi a szimbólumok olvasását (természetesen S0∈ Q).
F bizonyos Q állapotok egy halmaza (u.i. F⊂Q), az úgynevezett elfogadó állapotok.
A fentiek birtokában mondhatjuk, hogy az  nyelvet elfogadja egy determinisztikus véges állapotú automata (lásd később. δ meghatározása kicsit komplexebb egy nemdeterminisztikus véges állapotú automaták esetében) ahol:

Az automaták osztályai
A véges automaták a következő osztályokba sorolhatók:
determinisztikus véges állapotú automata  Az automata minden állapothoz és az ábécé minden szimbólumához tartozik egy átmeneti állapot.
nem determinisztikus véges állapotú automata  Az automata egy állapotához és egy ábécé szimbólumhoz nem tartozik átmeneti állapot, vagy több átmeneti állapot tartozik egy szimbólumhoz, illetve több szimbólumhoz ugyanaz az átmeneti állapot tartozik. Az automata akkor fogad el egy szót, ha létezik legalább egy olyan átmeneti állapot változási sorozat, út, ami az S0 állapotból kiindulva, a bemenetről olvasott szó hatására a kitüntetett F állapotok egyikébe vezet. Ha egy átmenet nem meghatározott, akkor az automata nem tudja, hogyan olvassa be a következő szimbólumot, megáll, és a szó visszautasított lesz.
 nem determinisztikus véges állapotú gép, ε átmenettel  a gép képes arra, hogy végre hajtson egy (vagy több) állapot változást úgy, hogy közben nem olvas be szimbólumot. Ha ezt a állapot változást -al jelöljük, akkor a nem determinisztikus véges állapotú automata kibővül egy -átmenettel. Azoknak az állapotoknak a halmazát, ahová q állapotból a fenti módszerrel el lehet jutni nevezik q -lezárásának.
Bebizonyítható, hogy a fenti automaták azonos nyelvet képesek elfogadni. Mindig lehetséges olyan determinisztikus véges állapotú gép szerkesztése, amely ugyanazt a nyelvet fogadja el, amelyet egy nem determinisztikus véges állapotú gép.

A véges automaták kiterjesztése
A fentiekben leírt automaták családja a nyelvek egy családját, a szabályos nyelveket fogadják el. Sok nagy teljesítményű automata képes sokkal bonyolultabb nyelveket elfogadni. Néhány automata ezek közül:
 verem automata ezek a gépek identikusak a determinisztikus véges állapotú gépekkel (vagy a nem determinisztikus véges állapotú gépekkel), azzal a különbséggel, hogy a működésükhöz kiegészítő memória szükséges a verem megvalósításához. A  átmeneti függvény most a verem tetején lévő szimbólum(ok)tól függ, és azt írja le, hogyan változik a verem tartalma az egyes átmeneteknél. A verem automaták a környezet független nyelveket fogadják el.
 Turing-gépek  Már csaknem nagy teljesítményű számítógépek. A gépek egy végtelen, szalag formájú memóriával, egy fejjel (amely a szalagot olvassa és módosítja, és amely valamelyik irányban mozog a szalag mentén) rendelkeznek. A Turing-gépek ekvivalensek bizonyos algoritmusokkal, és a modern digitális számító gépek elméleti alapját képezik. A Turing-gépek a rekurzívan felsorolható nyelveket fogadják el.
 lineárisan korlátos automata Egy lineárisan korlátos automata valójában egy korlátos Turing-gép; végtelen kapacitású szalag helyett a szalag méretével arányos hosszúságú string tárolására képes csak. A környezet függő nyelveket fogadja el.

A formális nyelvek Chomsky-féle hierarchiája

Angol nyelvű irodalom
 John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman – Introduction to Automata Theory, Languages, and Computation (2nd Edition)
 Michael Sipser, "Introduction to the Theory of Computation", 1997, | PWS Publishing, , Part One: Automata and Languages, chapters 1–2, pp. 29–122. Section 4.1: Decidable Languages, pp. 152–159. Section 5.1: Undecidable Problems from Language Theory, pp. 172–183.

További információk 
Vizuális Automata Szimulátor, angol nyelven

Formális nyelvek
Számítógép-tudomány
Automatika

en:Automata theory
ar:نظرية التشغيل الذاتي
de:Automatentheorie
es:Teoría de autómatas
fa:نظریه اتوماتا
fi:Automaattiteoria
fr:Théorie des automates
he:תורת האוטומטים
hr:Teorija automata
ja:オートマトン
ko:오토마타 이론
nn:Automatteori
no:Automatteori
pl:Teoria automatów
pt:Teoria dos autômatos
ro:Teoria automatelor
ru:Теория автоматов
sk:Teória automatov
sr:Teorija automata
th:ทฤษฎีออโตมาตา
uk:Теорія автоматів
zh:自动机