A PDA to test that the complement of a particular
language is a CFL
Prakash Panangaden
12th November 2018
We want to describe briefly and informally a pushdown automaton that
recognizes the context free language L where L = {ww|w ∈ Σ∗}.
If the length of a word is odd then it certainly is in L; testing to see if the
length is odd or even can be done by a DFA. Thus, the harder case is testing
to see if a word w is in L when |w| is even. In order to be in L, there must be
a pair of letters at positions i and j in w with wi 6= wj and with j = i+|w|/2;
i.e. i, j are at corresponding positions in the two halves of w. The idea is
that the PDA must guess where i and j are and also where the mid-point
is. Accordingly it stacks the input as it reads it. At some point it guesses
that it is looking at position i and it remembers in its finite-state memory
what the letter at this position is. At this point it keeps on reading input
letters and popping the stack. At some point the stack becomes empty, at
this point it will start stacking input letters again. Then it guesses where j
is and it compares the letter at position j with the letter in its finite-state
memory. Now if these letters are indeed mismatched it has to verify that
the position is correct. In order to do this it reads the rest of the input and
this time it pops the stack as it reads input letters. At the end of the input
the stack musy be empty. Why does this work? Let the string be of the
following form:
x1x2 . . . xi−1︸ ︷︷ ︸
(i−1) letters
xi
(n−i) letters︷ ︸︸ ︷
xi+1 . . . xn y1y2 . . . yi−1︸ ︷︷ ︸
(i−1) letters
yi
(n−i) letters︷ ︸︸ ︷
yi+1 . . . yn .
Now the machine has guessed that xi and yi are different letters and this
is what it checks. However, crucially, these must be verified to be in cor-
responding positions. In this case, it means that we have to check that
1
the length of the strings x1 . . . x(i−1)y(i+1) . . . yn is the same length as the
string x(i+1) . . . xny1 . . . y(i−1). This is exactly what the PDA does. It
stacks x1 . . . x(i−1), checks it off against x(i+1) . . . xny1 . . . y(i−1). The lat-
ter string must be longer so the stack will empty out before the string
x(i+1) . . . xny1 . . . y(i−1) is done. The PDA then switches to stacking the sym-
bols from the rest of x(i+1) . . . xny1 . . . y(i−1) and finally checks off its stacked
symbols against the last remaining piece of the input i.e. y(i+1) . . . yn.
2