Using Pushdown Automata to prove a language is context free

Question

How do I prove that the language L is a context free using Pushdown Automata? I would like to know the process of proving it. I am still new to CFLs and PDAs.

Answer 1

One way to solve the problem is first to find a context-free grammar that generates $L$. The following grammar does this. The non-terminals $X$ and $Y$ both generate the regular language $0+1$: each generates a single character that is either $0$ or $1$. $Z$ therefore generates the regular language $(0+1)^+$, $D$ generates the regular language $0(0+1)^*$, and $E$ generates the regular language $1(0+1)^*$.

$AD$ generates strings of the form $X^nE\#X^nD$ for some $n\ge 0$, which turn into terminal strings matching $$(0+1)^n1(0+1)^*\#(0+1)^n0(0+1)^*\;;$$ these differ in the $(n+1)$-st position. Similarly, $BE$ generates strings of the form $Y^nD\#Y^nE$, which turn into terminal strings matching $$(0+1)^n0(0+1)^*\#(0+1)^n1(0+1)^*\;,$$ which also differ in the $(n+1)$-st place.

$$\begin{align*} &S\to AD\mid BE\\ &A\to XAX\mid E\#\\ &B\to YBY\mid D\#\\ &X\to 0\mid 1\\ &Y\to 0\mid 1\\ &D\to 0\mid 0Z\\ &E\to 1\mid 1Z\\ &Z\to 0\mid 1\mid 0Z\mid 1Z \end{align*}$$

Now you can either convert this grammar to a pushdown automaton as explained (rather briefly) here, or you can try to use it as a model to construct a PDA directly. Remember that the PDA can be non-deterministic, so one idea is to let it test for inequality of the $n$-th input and the $n$-th input after the $\#$, where $n$ is chosen non-deterministically.