"Best practice" for finding the language of a formal grammar

Question

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!

Answer 1

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!