„Absztrakt automata” változatai közötti eltérés

; 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.

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 bemenetttőlbemenettő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 nyelv''nek nevezünk.

; [[veremautomata|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 nyelv]]ek elfogadására képesek.

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őlbemenetrő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épzenielké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ő estebenesetben pedig ''visszautasította'' azt. Az automata által elfogadott összes szó halmazát gyakran nevezik az ''automata által elfogadott nyelvnek''.

; Szó : Szimbólumok [[konkatenáció]]jával előállított, véges hosszúságú jelsorozat, vagy [[Stringstring]].

:…ahol ∑^* ∑ [[Kleene lezárás]]a

A fentiek birtokában mondhatjuk, hogy az <math>L</math> nyelvet elfogadja egy determinsztikusdeterminisztikus véges állapotú automata (lásd később. δ meghatározása kicsit komplexebb egy nemdeterminisztikus véges állapotú automaták esetében)<math>M=\langle Q, \Sigma, \delta, S_0, F\rangle</math> ahol:

A véges automaták a követekezőkövetkező osztályokba sorolhatók:

;[[determinisztikus véges állapotú gép|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ú gép|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 bemetrőlbemenetrő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ú automata|nem determinisztikus véges állapotú gép, &epsilon; á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 <math>\epsilon</math>-al jelöljük, akkor a nem determinisztikus véges állapotú automata ''kibővül'' egy <math>\epsilon</math>-átmenettel. Azoknak az állapotoknak a halmazát, ahová q állapotból a fenti módszerrel el lehet jutni nevezik q <math>\epsilon</math>-lezárásának.

A fentiekbanfentiekben leírt automaták családja a nyelvek egy családját, a [[szabályos nyelv]]eket fogadják el. Sok nagy teljesítményű automata képes sokkal bonyolultabb nyelveket elfogadni. Néhány automata ezek közül:

; [[Verem automaták|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ő [[számítógép memória|memória]] szükséges a [[verem (számítástechnika)|verem]] megvalósításához. A <math>\delta</math> átmeneti függvény most a verem tetején lévő szimbólum(ok)tól függ, éstés azt írja le, hogyan változik a verem tartalma az egyes átmeneteknél. A verem automaták a [[környezet független nyelv]]eket fogadják el.

; [[Turing-gép]]ek : 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ó nyelv]]eket fogadják el.

; [[lineárisan korlátos automata]]: Egy lineárisan korlátos automata valójában egy korátoskorlá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ő nyelv]]eket fogadja el.

* 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.&nbsp;29–122. Section 4.1: Decidable Languages, pp.&nbsp;152–159. Section 5.1: Undecidable Problems from Language Theory, pp.&nbsp;172–183.