12
$\begingroup$

This is a question from the Dragon book (I apologize for translation mistakes, I don´t have the English version on hand):

What language is generated by this grammar?

$S \rightarrow a S b S \mid b S a S \mid \epsilon$

I don't know what I'm supposed to do here. The definition in the book about languages says this (and that's pretty much it in the chapter):

a language is the set of all words that can be produced by any parse tree.

So, if I want to make "any" parse tree out of this grammar, I can recursively keep building it, using just the first two rules. I searched a bit and got the impression that every rule has to be used once, but I'm not sure. It would be very helpful if someone were able to provide some tips on solving these sorts of problems.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Hint: Use regular expression $\endgroup$
    – Bartosz Przybylski
    Commented Mar 18, 2013 at 22:20
  • $\begingroup$ For tips see answers below. In answer to your question: no, it is not necessary to use every rule at least once. Start with the start symbol (or axiom) and apply the rewrite rules until you are left with only terminal symbols (here lower case). $\endgroup$
    – Hendrik Jan
    Commented Mar 18, 2013 at 22:53
  • $\begingroup$ assuming the empty String is not a terminal Symbol, to my understanding it´s not possible that only terminal symbols are left, or am I missunderstand something? $\endgroup$
    – dan
    Commented Mar 19, 2013 at 6:17
  • $\begingroup$ Crossposted on cs.SE. $\endgroup$
    – Raphael
    Commented Mar 19, 2013 at 10:12
  • $\begingroup$ @dan. The empty string vanishes, so you can end up with terminals only: $S \Rightarrow aSbS \Rightarrow aaSbbS \Rightarrow aabbS \Rightarrow aabbbSa \Rightarrow aabbba$. For example. $\endgroup$
    – Hendrik Jan
    Commented Mar 19, 2013 at 11:04

2 Answers 2

Reset to default
7
$\begingroup$

Hint: What can you say about the number of $a$s and $b$s in the produced words?

It would be very helpful if someone were able to provide some tips on solving these sorts of problems.

There is no one-size-fits-all recipe here. It is undecidable in general, whether two CFGs produce the same language or two CFLs are the same language. A useful method is trying to notice the properties which remain invariant during the productions.

Improve this answer
$\endgroup$
6
$\begingroup$

Hint: Construct some words that are generated by this grammar. Do you see a pattern? Can you describe some properties of all words generated by the grammar, just by looking at the rules? Once you have a (correct) guess as to the language generated by the grammar, it won't be too difficult to prove it.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.