Absztrakt automata

A Wikipédiából, a szabad enciklopédiából

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

Alapozás[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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.
  • 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 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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

Definíciók[szerkesztés | forrásszöveg szerkesztése]

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 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
  • 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 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[szerkesztés | forrásszöveg szerkesztése]

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 \epsilon-al 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[szerkesztés | forrásszöveg szerkeszté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 \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 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

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

Referenciák[szerkesztés | forrásszöveg szerkesztése]

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman – Introduction to Automata Theory, Languages, and Computation (2nd Edition), Addison-Wesley,

Angol nyelvű irodalom[szerkesztés | forrásszöveg szerkesztése]

  • 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[szerkesztés | forrásszöveg szerkesztése]