DPDA · Deterministic context-free
The syntax of an arithmetic expression
Tokens n, +, *, ( and ): is this a well-formed expression? The machine alternates between expecting an operand and expecting an operator, and the stack holds one P per open parenthesis. A parser’s first job, without the parse tree.
The author’s examples, run
n → acceptn+n*n → accept(n+n)*n → accept((n)) → acceptn*(n+(n*n)) → acceptn+ → reject(n → rejectn)(n → reject() → rejectnn → reject