3
$\begingroup$

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!

  • 0
    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_".2012-06-20
  • 0
    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).2012-06-21
  • 0
    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)".2012-06-21
  • 0
    ok, you're right. So let's just say I want a mathematical definition of the set containing all words of that language, ok? ;)2012-06-21
  • 0
    "All words generated by such-and-such grammar" is a perfectly good mathematical definition.2012-06-21

1 Answers 1

2

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!