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: $\langle Q,\Sigma ,\delta ,S_{0},F\rangle$, 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:

$\delta :Q\times \Sigma \rightarrow Q.\,$

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

${\hat {\delta }}:Q\times \Sigma ^{\star }\rightarrow Q.$

Ahol ∑^* a ∑ lezárása.

• S₀ a kezdőállapot, amiben az automata áll, mikor még nem olvasott semmit a bemenetéről. (Természetesen S₀∈ Q)
• F állapotok halmaza (F∈Q), ezeket elfogadó állapotoknak nevezzük.

Ezek után mondhatjuk, hogy $L$ nyelvet az A determinisztikus automata elfogadja (Lásd lejjebb. δ definíciója egy kicsit komplikáltabb nemdeterminisztikus automatákra (NFA), ahol

$M=\langle Q,\Sigma ,\delta ,S_{0},F\rangle$ és $L=\{w\in \Sigma ^{\star }|{\hat {\delta }}(S_{0},w)\in F\}$

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 S₀-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 $\langle Q,\Sigma ,\delta ,S_{0},F\rangle$ 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ú

$\delta :Q\times \Sigma \rightarrow Q.$

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

${\hat {\delta }}:Q\times \Sigma ^{\star }\rightarrow Q.$

…ahol ∑^* ∑ Kleene lezárása

• S₀ a kiiduló állapot, azaz, ebben az állapotban van az automata, amíg el nem kezdi a szimbólumok olvasását (természetesen S₀∈ Q).
• F bizonyos Q állapotok egy halmaza (u.i. F⊂Q), az úgynevezett elfogadó állapotok.

A fentiek birtokában mondhatjuk, hogy az $L$ 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)$M=\langle Q,\Sigma ,\delta ,S_{0},F\rangle$ ahol:

$L=\{w\in \Sigma ^{\star }|{\hat {\delta }}(S_{0},w)\in F\}$

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 S₀ á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égrehajtson egy (vagy több) állapotváltozást úgy, hogy közben nem olvas be szimbólumot. Ha ezt a állapot változást $\epsilon$-nal jelöljük, akkor a nem determinisztikus véges állapotú automata kibővül egy $\epsilon$-átmenettel. Azoknak az állapotoknak a halmazát, ahová q állapotból a fenti módszerrel el lehet jutni, nevezik q $\epsilon$-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:

veremautomata

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 $\delta$ á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 veremautomaták a környezetfü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, és 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örnyezetfüggő nyelveket fogadja el.

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

Típus	Nyelvtan	Nyelv	Elfogadó automata
Type-0	Korlátozás nélküli	Rekurzívan felsorolható	Turing-gép
Type-1	Környezetfüggő	Környezetfüggő	Lineárisan korlátos
Type-2	Környezetfüggetlen	Környezetfüggetlen	Veremautomata
Type-3	Szabályos (reguláris)	Szabályos (reguláris)	Véges állapotú

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, ISBN 0-534-94728-X, 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