Skip to content

DPPDA

a modified deterministic pushdown automaton (DPDA) that puts to the stack a symbol with the pointer of the head’s position on the tape (from which the push has been performed). During the pop, the automaton has two options: either leave the head in the current position or move the head to the position stored in the pointer (retrieved during the pop of the symbol). We call this model a deterministic pointer pushdown automaton (DPPDA).

Computational Model for Parsing Expression Grammars, 2024

Can recognize PEG languages.

Open questions

  • Is it subclass of IPDA?
  • Is it subclass of 2DPDA?