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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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