# Find push down automata and context free grammar

I have the following language: $$L = \{a^nb^{2n+1} \mid n \ge 0\}$$

I must find the push down automaton and a context free grammar for the language.

For the push down I have no idea how to approach the problem.

For the context free grammar I think I know the solution: $$S \rightarrow Sb \\ S \rightarrow aSbb \\ S \rightarrow \lambda$$

• $S\to\lambda$ is no good. Try $S\to aSbb$, $S\to b$. – Hagen von Eitzen Jun 3 '13 at 13:23
• For the automaton: Did you prove the equivalence of the two concepts? Try to follow the general method given there to convert your grammar. – martini Jun 3 '13 at 13:23
• Hagen von Eitzen: I see now that I was wrong. – Dr.Optix Jun 3 '13 at 13:37

Here's the basic idea: Start by pushing a marker on the stack. Then, as long as the input character is $a$, push two markers on the stack. Then, for each $b$ read, pop a marker from the stack. If, after having read all the input, the stack is empty, then accept the input.

I've left it to you to complete this PDA to deal with, for example, incorrect inputs like $aba$ and $abbbb$.

• From this I understand that if my string is $aba$ the stack will evolve like: |, |||, || fro a, b and a respectivly. This means that if the stack is not empty and the input band is empty the string is rejected. Also if the stack is empty but the there are input symbols left, this is also a case when the grammar is not accepted. Right? – Dr.Optix Jun 3 '13 at 13:33
• @Dr.Optix Yes. Just build your PDA so that all of the "bad" cases like these are handled correctly. – Rick Decker Jun 3 '13 at 13:36

PDA: $$Starting States: S$$ $$Final States=\{END\}$$ $$\downarrow\downarrow\downarrow\downarrow\downarrow\downarrow\downarrow$$ $$\sigma(S,S)=a,BB|\epsilon$$ $$\sigma(S,\text{First})=b,\epsilon|B$$ $$\sigma(\text{First},\text{First})=b,\epsilon|B$$ $$\sigma(\text{First},\text{END})=b,\epsilon|B$$ Grammar: $$S\rightarrow aSbb$$ $$S\rightarrow b$$

Do you know how to construct a push down automaton that recognizes the language $L = \{a^nb^n | n\geq 0\}$? There is very similar construction for a push down automaton that recognizes your language.

Your CFG is almost correct, but you need to be a bit more careful; note that right now by just applying the first and third rules, you can get any string of the form $b^n$, which should not be in your language.

As a general note, if you have a CFG grammar, there is a simple construction of a PDA that recognizes the same language (see http://en.wikipedia.org/wiki/Pushdown_automaton#PDA_and_Context-free_Languages). In this case, though, it is easy to construct the PDA directly.