Language generated by a grammer

[Movingon]

Ok I have a simple question. Let us say we have a formal grammar, let us take this simple example:

S → aSb
S → ab

This grammar generates language a^n b^n. My question is, is there a way I can tell what kind of language this generates from the rules? I can of course apply the rules and find out this grammar can generate such a language but sometimes we may have more complex examples containing more rules. So my questions is, how can we then find out exactly the kind of language generated by a given grammar without having to manually apply rules as this may not be always practical? Thanks in advance!

 

[Bill Simpson]

"exactly the kind of language generated by a given grammar" is perhaps not precise enough to know exactly what kind of answer you want given any arbitrary grammar.

You can, by inspecting the form of the grammar and not manually applying the rules, probably determine which level of the Chomksy heirarchy the language resides in.

A few seconds of searching turns up one reasonable description of the heirarchy.
http://www.answers.com/topic/chomsky-hierarchy
There are many other well written descriptions of this out there.

If, as I suspect, you are looking for a more precise description of the language than this then I suspect the answer may be that you cannot determine this in every case by just inspecting the form of the grammar.

 

[Movingon]

Thanks. Yeah what I meant was describing more precisely and formally a language generated by a certain grammar, the Chomsky hierarchy I already know of. For example, you are given a grammar as follows: G = ({S, X}, {a, b}, P, S) with the rules:
P = {S → aaSbb | X | ε, X → Xb | ε}.

where ε here stands for the empty string. You are asked to find out and describe formally the language generated by this grammar. As it turns out, this grammar generates language L = {a^n b^{2n+m} | n \geq 0, m \geq 0}

So my question is, how could I, for example, figure out that this grammar generates this language? Do I have to apply those rules and then from the result find out the kind of language generated? Is this the only way to find out a language L generated by grammar G?