Automata magazinmemóriával

Az automataelméletben a lenyomó automata egy véges állapotú gép , amely egy verem segítségével tárolja az állapotokat.

Formális definíció

A közönséges véges automatákkal ellentétben a lenyomó automata egy halmaz [1]

M=(K,\Sigma ,\pi ,s,F,S,e),

ahol

K az automata állapotok véges halmaza,

s\in K

az automata egyetlen megengedett kezdeti állapota,

F\subseteq K

— végső állapotok halmaza, és F=Ø és F=K megengedett, Σ egy érvényes bemeneti ábécé, amelyből az automata által beolvasott karakterláncok keletkeznek, S - a memória ábécéje (üzlet),

e\in S

egy null memóriakarakter.

A memória úgy működik, mint egy verem , vagyis a hozzá írt utolsó elem elérhető olvasásra. Tehát az átmeneti függvény egy leképezés . Vagyis az aktuális állapot, a bemeneti szimbólum és az áruház tetején lévő szimbólum kombinációja alapján az automata kiválasztja a következő állapotot, és esetleg azt a szimbólumot, amelyet a boltba ír. Abban az esetben, ha az automata szabály jobb oldali részében jelen van , akkor semmi sem kerül hozzáadásra az áruházhoz, és a felülről származó elem törlődik. Ha a bolt üres, akkor a bal oldalon lévő c szabályok lépnek életbe. $\pi :K\times \Sigma \times S\to K\times S$ $e$ $e$

A push-down automaták által felismert nyelvek osztálya megegyezik a környezetfüggetlen nyelvek osztályával .

Tiszta formájában a push-pull automatákat ritkán használják. Általában ezt a modellt a közönséges véges automaták és a szintaktikai nyelvtan közötti különbség megjelenítésére használják . A lenyomó automaták megvalósítása abban különbözik a véges automatáktól, hogy az automata aktuális állapota erősen függ bármely korábbi állapottól.

Példa egy lenyomó automata használatára

ismétlés X := top shop szimbólum ; ha X = terminál vagy $ , akkor ha X = InSym , akkor távolítsa el az X -et az áruházból ; InSym := következő szimbólum ; else error () end else /* X = nem -terminális */ if M [ X , InSym ] = X -> Y1Y2 ... Yk akkor töröld X -et a tárolóból ; tegye Yk , Yk - 1 , ... , Y1 raktárba ( Y1 felül ) ; _ kimeneti szabály X -> Y1Y2 ... Yk else error () /* táblabejegyzés M üres */ vége addig , amíg X = $ /* tároló üres */

A push-pull automaták típusai

Vannak determinisztikus és nem determinisztikus lenyomó automaták.

A nem determinisztikus automatákhoz (a determinisztikusakkal szemben) két egyenértékű befejezési feltétel létezik:

üres bolt,
a végállapot elérése.

Egy determinisztikus automata csak akkor fejeződik be, amikor eléri a végső állapotot.

Lásd még

A JFLAP egy cross-platform automata szimulátor, Turing-gép, nyelvtan, automata gráfot rajzol.

Jegyzetek

↑ Discrete Mathematics, 2006 , p. 630.

Irodalom

John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Bevezetés az automataelméletbe, a nyelvekbe és a számításba. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .
Belousov A. I., Tkachev S. B. Diszkrét matematika. — M .: MGTU , 2006. — 743 p. — ISBN 5-7038-2886-4 .

Formális nyelvek és formális nyelvtanok
Általános fogalmak	Chomsky-hierarchia Ábécé Szó
Típus 0	Korlátlan nyelvtan Turing gép felsorolt nyelv Feloldható nyelv
1. típus	Környezetérzékeny nyelvtan Környezetérzékeny nyelv Lineárisan korlátos automata
2. típus	Kontextus mentes nyelvtan Kétértelmű nyelvtan Kontextus mentes nyelv Lenyomó automata ( determinisztikus ) Növekedési Lemma Ogden Lemma Cook-tétel
3. típus	Szabályos nyelvtan szabályos nyelv Reguláris kifejezés Állapotgép ( determinisztikus , nem determinisztikus ) DFA minimalizálás Az NFA meghatározása Myhill-Nerode tétel
elemzése	LL analizátor LR elemző Rekurzív süllyedés módszere Kok-Younger-Kasami algoritmus