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.
The author’s examples, run
ε → acceptabc → acceptaacc → acceptaaabbccc → accepta → rejectbbc → rejectbacc → rejectbaabbccc → reject