Automatická s pamětí zásobníku

V teorii automatů je zásobníkový automat konečný stavový automat , který používá zásobník k ukládání stavů.

Formální definice

Na rozdíl od běžných konečných automatů je zásobníkový automat množina [1]

kde

K je konečná množina stavů automatu, je jediný povolený počáteční stav automatu, — množina konečných stavů a ​​F=Ø a F=K jsou přípustné, Σ je platná vstupní abeceda, ze které se tvoří řetězce, které automat čte, S - abeceda paměti (ukládání), je znak nulové paměti.

Paměť funguje jako zásobník , to znamená, že poslední zapsaný prvek je k dispozici pro čtení. Přechodová funkce je tedy mapování . To znamená, že na základě kombinace aktuálního stavu, vstupního symbolu a symbolu v horní části úložiště vybere automat další stav a případně symbol, který se má do úložiště zapsat. V případě, že je přítomen v pravé části pravidla automatu , není do úložiště nic přidáno a prvek shora je vymazán. Pokud je úložiště prázdné, spustí se pravidla c na levé straně.

Třída jazyků rozpoznávaných zásobníkovými automaty je stejná jako třída bezkontextových jazyků .

V čisté formě se push-pull automaty používají jen zřídka. Typicky se tento model používá k vizualizaci rozdílu mezi obyčejnými konečnými automaty a syntaktickými gramatikami . Implementace zásobníkových automatů se liší od konečných automatů tím, že aktuální stav automatu silně závisí na jakémkoli předchozím.

Příklad použití zásobníkového automatu

repeat X := symbol top obchodu ; pokud X = terminál nebo $ , pak pokud X = InSym , odeberte X z úložiště ; InSym := další symbol ; else error () end else /* X = non -terminal */ if M [ X , InSym ] = X -> Y1Y2 ... Yk then delete X from store ; dát Yk , Yk - 1 , ... , Y1 na sklad ( Y1 nahoře ) ; výstupní pravidlo X -> Y1Y2 ... Yk else error () /* záznam v tabulce M je prázdný */ end end dokud X = $ /* obchod je prázdný */

Typy push-pull automatů

Existují deterministické a nedeterministické zásobníkové automaty.

Pro nedeterministické automaty (na rozdíl od deterministických) existují dvě ekvivalentní ukončovací kritéria:

  1. prázdný obchod,
  2. dosažení koncového stavu.

Deterministický automat končí, až když dosáhne konečného stavu.

Viz také

  • JFLAP  je multiplatformní simulátor automatů, Turingův stroj, gramatika, kreslí graf automatu.

Poznámky

  1. ↑ Diskrétní matematika, 2006 , str. 630.

Literatura

  • John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Úvod do teorie automatů, jazyků a počítání. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .
  • Belousov A. I., Tkachev S. B. Diskrétní matematika. — M .: MGTU , 2006. — 743 s. — ISBN 5-7038-2886-4 .
 Formální jazyky a formální gramatiky
Obecné pojmy
Typ 0
Typ 1
Typ 2
Typ 3
rozebrat