Library

NPDA · Context-free

aⁱbʲcᵏ with i = j or j = k

Either the a’s match the b’s, or the b’s match the c’s. A pushdown machine guesses which, at the start. No grammar for this language is unambiguous: aⁿbⁿcⁿ satisfies both conditions and always has two derivations.

starta1a2b1c1done1b2c2done2
The machine as drawn — 9 states, 14 transitions.

The author’s examples, run

ε → acceptabc → acceptaabbcc → acceptaaabbbccccc → acceptb → rejectbbc → rejectbabbcc → rejectbaabbbccccc → reject