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

$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.


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.

  • 1
    $\begingroup$ en.wikipedia.org/wiki/Context-free_language#Automata, en.wikipedia.org/wiki/… $\endgroup$
    – D.W.
    Commented Jan 29, 2020 at 18:29
  • $\begingroup$ The set of context free languages include exactly those accepted by a PDA. $\endgroup$ Commented Jan 29, 2020 at 18:41
  • 2
    $\begingroup$ The problem here is that your PDA doesn't recognize $L$ but rather $\{1^mx1^n=1^{m+n}\}$. $\endgroup$ Commented Jan 29, 2020 at 22:35
  • $\begingroup$ @RickDecker Make an answer? $\endgroup$ Commented Jan 30, 2020 at 0:53
  • $\begingroup$ @YuvalFilmus Nah. Too small to rate as an answer. Feel free, though. $\endgroup$ Commented Jan 30, 2020 at 16:51

1 Answer 1


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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.