[Solved]: Approaches to Solve PDA

Problem Detail: 

There is a saying by Computer Science Professor's everywhere :

PDA Checks the intelligence of Students, as certainly there is no approach except power and imagination of mind to solve problems and design PDA... 

While thinking today i thought How can we design automata of a^2n b^(2n-1)

I tried my best : For example let q0 is initial state and top of the empty stack has Z.

So, Let say Transition of (q0, a , Z) = (q1,Z)              Transition of (q1, a , a) = (q1,a)              Transition of (q1, b , a) = (q2,-)              Transition of (q2, $ , Z) = (qf,Z) 

I was able to solve this problem all of a sudden...

My doubt is still the same, How to be the best in solving PDA problems and Is there any way to define a strategy to solve problems ?

P.S. Your comments are welcome if i did something wrong in above stated question

Asked By : Shubham

Answered By : Patrick87

One technique is to start out with a context-free grammar, and apply an algorithm to get a corresponding PDA. Often, writing a grammar might be a bit easier than writing the PDA directly. In this case, it seems (to me) to be fairly easy to arrive at the grammar $S \rightarrow aaSbb \mid aab$, from which a PDA follows by construction (see this, for example, for some info on how to do such a conversion, if this is new to you)

If you want to build the PDA directly, another way to think about it is to start from the end of strings, and ask yourself what needs to be on the stack to make it easy to tell you need to accept the string. In your case, if you're looking at the last part of the string - say, you've started seeing $b$'s, what would it be really helpful to have on the stack? Well, the easiest thing would be to have $2n-1$ symbols on the stack. If we can arrange that, then when we get to $b$'s we can simply pop one symbol off the stack for every $b$ we read, and accept if the stack is empty when we're done with the input. How can we leave $2n-1$ symbols on the stack after reading $2n$ of the $a$ symbol? Well, we could put a symbol on the stack each time we read an $a$, and then, before we start reading $b$'s, remove one symbol from the stack. We get three phases to the computation: (1) read an even number of $a$'s and push a symbol onto the stack for each $a$ you read; (2) remove one symbol from the stack; (3) read $b$'s until the stack is empty and/or you run out of input. We'd get a PDA like this:

q    s    e    q'    s' --   --   --   --    -- q0   Z    a    q1    aZ q0   a    a    q1    aa q0   a    -    q2    - q1   a    a    q0    aa q2   a    b    q2    - q2   Z    -    q3    Z 

We have start state q0 and accepting state q3. Entries of - in the e column indicate $\lambda$-transitions, whereas entries of - in s' indicate popping a symbol off the stack.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16308