Library

NPDA · Context-free

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

Sipser’s example of a language that needs nondeterminism. Push the a’s; then guess whether they will be matched by the b’s or by the c’s, and skip the other block. Not to be confused with i = j or j = k, which has its own entry.

sp1p2c1r2f2
The machine as drawn — 6 states, 10 transitions.

The author’s examples, run

ε → acceptabc → acceptaacc → acceptaaabbccc → accepta → rejectbbc → rejectbacc → rejectbaabbccc → reject