4. Nedeterministické zásobníkové automaty (akceptory) a jejich vztah k bezkontextovým jazykům

Question 1

Nedeterministické zásobníkové automaty

Answer 1

jsou to abstraktní modely výpočtu, které se používají k rozpoznávání jazyků

Jsou obdobou nedeterministických konečných automatů, avšak mají navíc zásobník, na který mohou ukládat a odebírat symboly

NZA může být popsán pomocí stavového diagramu, kde každý uzel reprezentuje stav automatu a šipky mezi nimi představují přechody podle vstupních symbolů a symbolů na vrcholu zásobníku

Question 2

Postup NZA

Answer 2

1, Nejprve automat v každém kroku přečte jeden symbol ze vstupu a jeden symbol ze zásobníku
2, Podle toho se přesune do nového stavu a případně nahradí symbol na vrcholu zásobníku jiným symbolem
3, Pokud automat dosáhne koncového stavu a zároveň se na vrcholu zásobníku nachází speciální symbol $ (označující prázdný zásobník), pak akceptuje vstupní řetězec

Question 3

Vztah k bezkontextovým jazykům

Answer 3

Každý bezkontextový jazyk lze rozpoznat pomocí NZA a naopak

Každý NZA lze převést na bezkontextovou gramatiku, která generuje jazyk, který tento automat rozpoznává

Tento postup lze provést například pomocí konstrukce zásobníkového automatu z bezkontextové gramatiky

V důsledku toho jsou nedeterministické zásobníkové automaty často používány k analýze a zpracování bezkontextových jazyků, zejména v oblastech jako jsou překladače, kompilátory nebo syntaktická analýza programů