Absztrakt automata

A Wikipédiából, a szabad lexikonból.

Az automaták elmélete az informatika egy területe, ami véges állapottérrel rendelkező gépekkel (azok matematikai reprezentációival, automatákkal, Turing-gépekkel) foglalkozik. Alább röviden bemutatjuk az automatákat és működésüket.

Tartalomjegyzék

[szerkesztés] 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 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.

[szerkesztés] Automata

[szerkesztés] Alapozás

Az automata a matematikai modellje egy véges állapotokkal rendelkező 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 bemenetttő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.

[szerkesztés] 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.
  • 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\}

[szerkeszté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.

[szerkesztés] 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. Turnig-géppel bármilyen algoritmus megvalósítható. Ő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.

[szerkesztés] Referenciák

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