Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If I've been given a formal grammar like

$$ \begin{eqnarray} S & \Rightarrow & \lambda & | & 0A & | & 1B \\ A & \Rightarrow & 1S & | & 0AA \\ B & \Rightarrow & S & | & 0S & | & 1BB \end{eqnarray} $$

what is "the best" (or just a "good") way to find the language of that grammar?

I do have a problem with that kind of exercises. I play around with the production rules and sometimes I find a solution - sometimes I don't.

Could you please help me to find a "blueprint" for that kind of excercise? Or could you tell me how you would approach this one?

Thanks in advance!

share|improve this question
That depends a lot of which form you want the result in. How do you expect the answer (i.e. the language) to be written down when you're done? A common way to specify a language is just by giving a grammar that generates it -- but that can't be what you want here, because then what you already have would be a perfectly good answer. So it makes no sense to ask "find the language" -- your question needs to be "describe the language in such-and-such particular form". –  Henning Makholm Jun 20 '12 at 21:50
The answer should be either a regular expression (if possible) or a mathematical set (just like $L = \{ 0^a1^b \; | a \geq b \} $). It should be clear what kind of words the language contains. If you look at the grammar I provided you can't see what words are inside just by looking at it (at least I can't). –  muffel Jun 21 '12 at 7:40
Even figuring out whether a given context-free grammar describes a regular language is known to be an undecidable problem, so there is no procedure that produces "a regular expression (if possible)". –  Henning Makholm Jun 21 '12 at 10:30
ok, you're right. So let's just say I want a mathematical definition of the set containing all words of that language, ok? ;) –  muffel Jun 21 '12 at 12:01
"All words generated by such-and-such grammar" is a perfectly good mathematical definition. –  Henning Makholm Jun 21 '12 at 13:03
add comment

1 Answer

up vote 2 down vote accepted

This probably shouldn't be posted as an answer to your question, but it's likely going to turn out to be way too long to be a comment. Your sample grammar was well-chosen, since none of the suggestions I'll propose seem to apply.

It appears as if you have had sufficient exposure to grammars and languages to realize that simple grammars can sometimes generate languages that are very hard to describe in any succinct form and, conversely, that some really messy and complicated grammars generate languages that are quite easy to describe. As for a "blueprint", depending on what metrics you put on the description of a language I'd be pretty confident in saying there's no possible algorithm that will take a grammar and provide a "reasonable" description of the language it generates, other than the completely uninteresting description "it's the language generated by this grammar".

That said, there are some techniques I use (and I suspect you know already) that can sometimes be helpful. In no particular order:

  • Does the grammar look like anything you've worked on before? Yeah, that's obvious, but it points out the fact, particularly comforting to us older theorists, that sometimes experience can be even better than brilliance.
  • Is the grammar in a particularly nice form? Obviously, a left-linear grammar, for example, will make your job a lot easier. Failing that, perhaps it's in a normal form like Chomsky or Griebach or can be transformed to be one. That may or may not help. Is it even a context-free grammar? If it's not your task is often going to be really hairy.
  • Can you start with some "base" production $A\rightarrow \alpha_1\, |\, \alpha_2\, | \dots$ for some sentential forms $\alpha_i$ and get a simple description of the strings generated by $A$ and then use those in the other productions with $A$ on the right side?
  • Related to the above, are there any productions that aren't (directly or indirectly) recursive? Concentrate your efforts on them.
  • Are there any mostly-recursive productions like $P\rightarrow aP\, |\, bP\, |\, Q$? Sometimes these generate easily-described strings.

There are probably many others that I've missed, but I'm going home to eat before hypoglycemia sets in. Good luck!

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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