3
$\begingroup$

I'm trying to convert a context free grammar to a pushdown automaton (PDA); I'm not sure how I'm gonna get an answer or show you my progress as it's a diagram... Anyway this is the last problem I have on a homework that's due later today, so I'd appreciate some kind of help, even if it's just an explanation of the correct answers diagram. I need a PDA corresponding to this CFG:

$$S \rightarrow aSa | bSb | B$$ $$B \rightarrow bB | \epsilon$$

I know it will have to push X every time 'a' is read before a 'b', and pop X every time 'a' is read after a 'b'. But I'm not sure how to arrange the PDA in order to tell which a's came after b's. Also, I'm unsure of how to deal with the b's in terms of the stack, as there can be as many in the middle of the string as you want. Help appreciated.

Thanks, Pachun

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ The singular form of "automata" is "automaton". $\endgroup$
    – JeffE
    Jul 15, 2012 at 2:42
  • $\begingroup$ You ask us to solve your homework in time for the hand-in, seriously? Anyway, there are simple standard algorithms for this conversion which were either presented in lecture or can be found in your textbook; check the proof(s) that CFG and NPDA have the same power. $\endgroup$
    – Raphael ♦
    Jul 18, 2012 at 0:49

1 Answer 1

Reset to default
2
$\begingroup$

This is basically the language of all palindromes over $\{a, b\}$ which can contain an arbitrary number of $b$'s in the middle. First, you could build a PDA for palindromes. This is a fairly standard language, so you should be able to find plenty to get you started. Then, you need to add a way to read an arbitrary number of $b$'s after you're done pushing new symbols to the stack, and before you start popping symbols. So the basic steps here:

  1. Read $a$'s and $b$'s and push to the stack;
  2. Read any number of $b$'s;
  3. Read $a$'s and $b$'s and pop from the stack.

Please let me know if you need more guidance. Note that you're going to need to use nondeterminism here, so don't worry about it. This is a not a deterministic language (unless I'm mistaken... which has happened before).

Improve this answer
$\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.