„Absztrakt automata” változatai közötti eltérés
| [nem ellenőrzött változat] | [nem ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a interwikik új sorba rendezése |
a kozmetikai javítások |
||
15. sor:
Formálisan az automatát egy [[rendezett N-es|rendezett 5-ös]] írja le: <math>\langle Q, \Sigma, \delta, S_0, F\rangle</math>, ahol:
*Q az ''állapotok'' véges halmaza,
*
*
<center><math>\delta:Q \times \Sigma \rightarrow Q.\,</math></center>
:A függvény kiterjeszthető úgy, hogy ne csak egy betűt, hanem egy egész szót fogadjon:
<center><math>\hat\delta:Q \times \Sigma^{\star} \rightarrow Q.</math></center>
:Ahol ∑<sup>*</sup> a ∑ [[lezárás]]a.
*S<sub>0</sub> a kezdőállapot, amiben az automata áll, mikor még nem olvasott semmit a bemenetéről. (Természetesen S<sub>0</sub>
*F állapotok halmaza (
Ezek után mondhatjuk, hogy <math>L</math> nyelvet az A determinisztikus automata elfogadja (Lásd lejjebb.
<math>L= \{ w \in \Sigma^{\star}|\hat\delta(S_0,w)\in F\}</math></center>
30. sor:
;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 S<sub>0</sub>-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,
===Automaták kiterjesztései===
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
; [[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ó. Ő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.
| |||