# Push-down Automata Construction

Construct a push-down automata to recognize the language $A = \{u\#v \in \{0,1,\#\}^{*} | u = v^{\complement} \}$. Here, $v^{\complement}$ is the bit-complement of v.

I don't see how to perform this with a LIFO stack. I would like some hints (not a solution) if possible.

Thanks,

## 1 Answer

There is no such PDA because $A$ is not context-free. This can be proved by pumping.