Using Pushdown Automata to prove a language is context free 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.
 A: 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.
