0
$\begingroup$

Im a novice trying to understand the theory of computation.Im trtying to learn about PDA.I understand that it is a machine counterpart of CFG.Im basically referring to Introduction to Automata Theory by John E. Hopcroft and Jeffrey D.Ullman and this video http://youtu.be/8O6FUFwWt5A?t=6m32s by IIT Professor Kamala

I understand the plates placed above spring analogy.What confuses me is that the reference example.It uses a table like the one shown here http://youtu.be/8O6FUFwWt5A?t=6m32s

Where do we get this table and can i use this table for all languages?

Like if a question comes up like this

enter image description here

Can i use the same table and what im supposed to do? I know it might sound stupid,but please help me,im trying to learn.

$\endgroup$
  • $\begingroup$ In this example, you can use the stack to store the expected number of 'b's, but when you are done with this, try $\{a^{2n}b^n: n\geq 1\}$. Then you will be able to solve $\{a^{pn}b^{qn}: n\geq 1\}$ for some fixed positive integers $p,q$. $\endgroup$ – user1537366 Dec 8 '14 at 13:23
1
$\begingroup$

Try to analice the language you want to build a PDA for. Have you seen the standard example for the language $\{a^nb^n\mid n\in\mathbb N\}$? (I guess this should be in the book you cite.)

What would you do to implement a PDA for this simpler example? What are the states and what is the role of the stack in this example (it is used to store $a$'s so you can count/determine whether the number of $b$'s matches with the number of $a$'s).

Now for the example you are interested in, what is the difference (now the number of $a$'s and $b$'s is not the same, but there is still a strong connection between them). Can you modify the PDA for the language $\{a^nb^n\mid n\in\mathbb N\}$ to build one for your example?

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