Deterministički potisni automat: razlika između inačica

 

Dva su moguća kriterija prihvaćanja niza znakova: prihvaćanje ''praznim stogom'' i prihvaćanje ''prihvatljivim stanjem''. Lako se može pokazati da su oba kriterija istovjetna: konačno stanje može u petlji uzimati znakove sa vrha stoga sve dok se sadržaj stoga ne isprazni, a i stroj može detektirati prazni stog i preći u prihvatljivo stanje detektiranjem jedinstvenog znaka kojeg na vrh stoga dodaje početno stanje.

 

{{Formalni jezici i gramatike}}