„Absztrakt automata” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a Bot: következő hozzáadása: simple:Automaton |
|||
37. sor:
A fent leírt automaták által elfogadott nyelvek családja a [[reguláris nyelv]]ek családja. Más automaták komplikáltabb nyelveket is képesek elfogadni. Ilyen automaták például:
; [[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.
; [[Turing-gép]]ek : 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ő nyelv]]eket tudnak elfogadni.
| |||