3
$\begingroup$

I have the following CFG $G$: $$ \begin{align} S &\rightarrow aAbb \mid aaBb \\ A &\rightarrow aAbb \mid \epsilon \\ B &\rightarrow aaBb \mid \epsilon \\ \end{align} $$

I have to create a PDA (pushdown automaton) to recognize this language however I am unsure on how to do it. So far I have this(revised based on feedback from user Hendrik Jan) :

enter image description here

I understand that it should accept the last one ($aaaabb$) however it does not for the current version.

$\endgroup$
1
$\begingroup$

From CFG to PDA is a simple construction. Set axiom $S$ as initial pushdown symbol. If the topmost symbol of the stack is nonterminal replace it according to a production of the grammar. If the topmost symbol is a terminal we are forced to read the same symbol from input tape (and pop the symbol). That is called expand-match. See wikipedia. The resulting PDA is single state, acceptance by empty stack.

(added) Your problem is on a special type of grammar, linear context-free. That means in every step of the derivation there is exactly one nonterminal. You can mimic this using a different construction. Basically the nonterminal is the state. All terminal symbols to the left are read, those to the right are pushed, to be read later. For $S\to aaBb$ the PDA goes from state $S$ to state $B$ while reading $aa$ (in usual models that takes two steps) and pushing $b$.

On your construction (it seems of the latter type). Concretely: the grammar generates $a$'s and $b$'s in a two-to-one / one-to-two ratio. In general: in order (for yourself) to see why it doesn't work you have to try to formulate the meaning of the states. How do they relate to things happening in the grammar?

$\endgroup$
  • $\begingroup$ Thanks firstly for responding however can you provide a diagram to your explanation because the current diagram was based on what you've stated in that I'd considered the PDA for only aAbb(hence the top half of the diagram),and then the aaBb(hence the bottom half). However I was not sure on what you meant by the having a non terminal? I have updated the diagram based on your feedback. $\endgroup$ – Anish B May 8 '13 at 11:46
1
$\begingroup$

While Hendrik Jan's answer is totally spot-on, it's worth noting that you don't always need to follow the algorithmic construction to get a PDA. If you can decide via analysis what the language is, you can often come up with a machine more easily.

The grammar you give generates $a^nb^{2n} \cup a^{2n}b^n$ where $n > 0$. In particular, any construction which uses the rule $S \rightarrow aAbb$ will generate a string in $a^nb^{2n}$, and any construction using the rule $S \rightarrow aaBb$ will generate a string in $a^{2n}b^n$.

Therefore, a simple procedure to obtain a correct PDA is the following:

  1. Create a PDA $M_1$ to recognize $a^nb^{2n}$ for $n > 0$.
  2. Create a PDA $M_2$ to recognize $a^{2n}b^n$ for $n > 0$.
  3. Create a PDA $M$ which recognizes $L(M_1) \cup L(M_2)$.

Each of these steps is significantly easier than trying to create a PDA from the original grammar, in my opinion, anyway.

For (1), push two $a$'s onto the stack for each $a$ you read, then pop an $a$ each time you read a $b$. Accept if the stack is empty once the input is gone.

For (2), push an $a$ for every two $a$'s you read, then pop an $a$ for each $b$ you read. Accept if the stack is empty once the input is gone.

For (3), you can create a new initial state and non-deterministically jump to the initial state of either $M_1$ or $M_2$ without consuming any input or putting anything on the stack. This will ensure that if your input represents a string accepted by either of the automata, then there will be a path that accepts the input.

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