1
$\begingroup$

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.

$\endgroup$
5

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

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

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