# Can there be a language not Context free but still PDA acceptable?

Let the input alphabet be $$Σ = \{1,x,=\}$$
Let the stack alphabet be $$\tau = \{1,\\}$$ where $$\$$ is the initial stack symbol.

Let,
$$q_0$$ be the initial state of the PDA,
$$q_f$$ be the final state of PDA,
I can define a transition function for PDA like this.

$$(q_0,1,\)\rightarrow(\1,q_1)$$
$$(q_1,1,1)\rightarrow(1,q_1)$$
$$(q_1,x,1)\rightarrow(1,q_2)$$
$$(q_2,1,1)\rightarrow(1,q_2)$$
$$(q_2,=,1)\rightarrow(1,q_3)$$
$$(q_3,1,1)\rightarrow(\epsilon,q_3)$$
$$(q_3,\epsilon,\)\rightarrow(\,q_f)$$

Now the PDA can recognize language $$L = \{1^m x 1^n = 1^{mn}\}$$ But According to https://web.stanford.edu/class/archive/cs/cs103/cs103.1142/lectures/18/Small18.pdf Slide 24 this language is not Context Free.

Assume that I am quite beginner in TOC.

• – D.W. Jan 29 '20 at 18:29
• The set of context free languages include exactly those accepted by a PDA. – Ṃųỻịgǻňạcểơửṩ Jan 29 '20 at 18:41
• The problem here is that your PDA doesn't recognize $L$ but rather $\{1^mx1^n=1^{m+n}\}$. – Rick Decker Jan 29 '20 at 22:35
• @RickDecker Make an answer? – Yuval Filmus Jan 30 '20 at 0:53
• @YuvalFilmus Nah. Too small to rate as an answer. Feel free, though. – Rick Decker Jan 30 '20 at 16:51

## 1 Answer

It is proven in your nearby language theory textbook (like Hopcroft, Motwani, Ullman "Introduction to automata theory, languages, and computation" (3rd edition, Pearson) that the languages accepted by (nondeterministic) PDAs are exactly the context free languages (generated by context free grammars).