Search code examples
computation-theorypushdown-automaton

How does a pushdown automaton know how to read a palindrome?

For example, how does a PDA know how to read a palindrome in L = {a, b}*?

PDA that accepts palindromes over {a,b}* :

image

So, based on my drawing of the PDA:

How does it know when the first half of the string is on the final terminal (letter of the alphabet), and therefore knows to go from state 0 to state 1 (and furthermore knowing to "pop" letters from the stack backwards, hence creating the palindrome)?

Solution

  • This is a nondeterministic pushdown automata. The answer to your question is that it guesses and may be assumed to guess correctly. Nondeterministic automata accept a string w if any path along which w might be processed results in w's being accepted.

    If we define acceptance as having an empty stack in an accepting state, then the only way something can be accepted by the above NPDA is if:

    • it puts some stuff on the stack in state q0
    • it eventually guesses that it needs to read the second half of the string
    • it reads what it pushed onto the stack, but backwards, in q1

    There are three "guesses" that the NPDA makes:

    1. it guesses that the string is an even-length palindrome when it guesses e e/e, where e is used in place of lambda.
    2. it guesses that the string is an odd-length palindrome with a in between the two halves when it guesses a e/e, where e is used in place of lambda
    3. it guesses that the string is an odd-length palindrome with b in between the two halves when it guesses b e/e, where e is used in place of lambda

    Each of the above three guesses is also guessing that the first half of the string, excluding a possible middle element, has been seen already.

    This guess will eventually be true for any palindrome, and it won't be true for anything but a palindrome, so the NPDA accepts PAL.