Automata-elmélet

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

Az elméleti számítógép tudományban, az automata-elmélet az absztrakt gépek elméletével és azok problémáival foglalkozik, illetve megoldást keres azokra. 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.

Tartalomjegyzék

1 Alapok
2 Formális leírás
- 2.1 Definíciók
3 Az automaták osztályai
- 3.1 A véges automaták kiterjesztése
4 Külső hivatkozás
5 Angol nyelvű irodalom

[szerkesztés] 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 bementrő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épzeni, 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ő esteben pedig visszautasította azt. Az automata által elfogadott összes szó halmazát gyakran nevezik az automata által elfogadott nyelvnek.

[szerkesztés] Formális leírás

[szerkeszté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 szoimbó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

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 determinsztikus 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\}$

[szerkesztés] Az automaták osztályai

A véges automaták a követekező 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.
nemdeterminisztikus 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 állapotváltozási sorozat, út, ami az S₀ állapotból kiindulva, a bemetrő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.
nemdeterminisztikus 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 állapotváltozást $ε$ -al jelöljük, akkor a nemdeterminisztikus 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 nemdeterminisztikus véges állapotú gép.

[szerkesztés] A véges automaták kiterjesztése

A fentiekban leírt automaták családja a nyelvek egy családját, a szabályos nyelveket fogadják el. Sok nagyteljesí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 nemdeterminisztikus véges állapotú gépekkel), azzal akü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, ést 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, 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 korá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ö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ú

[szerkesztés] Külső hivatkozás

Vízuális Automata Szimulátor, angol nyelven

[szerkesztés] 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. hu:Absztrakt automata

A lap eredeti címe "http://hu.wikipedia.org../../../a/u/t/Automata-elm%C3%A9let.html"

Kategória: Formális nyelvek