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
$$
 A: 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$.
A: 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$$
A: 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.
