Library

NPDA · Context-free

Two different words: x#y with x ≠ y

Equal words x#x are beyond a stack, but different ones are not. Either the lengths differ, which a stack measures, or there is a position where they disagree: guess it, push one marker per letter before it, remember the letter, and pop the markers off against y to reach the same position there.

startlenposylenshorterlongersawAsawByAyBdiffer
The machine as drawn — 11 states, 30 transitions.

The author’s examples, run

#a → accepta#baabb → acceptab# → acceptaaaaaba#bbb → acceptaa → reject##baabb → reject#b# → reject#aaaaba#bbb → reject