# 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