Library

DPDA · Deterministic context-free

One else too many

Hopcroft, Motwani and Ullman’s if/else example: i is an if, e an else, and the machine stops at the first else that has no if to match. It accepts exactly the strings where that happens at the last symbol — in the book by emptying its stack, here by moving to a final state when it would have.

qf
The machine as drawn — 2 states, 3 transitions.

The author’s examples, run

e → acceptiee → acceptieiieee → acceptieieiieee → accepti → rejecteee → rejecteeiieee → rejecteeieiieee → reject