CODEWITHSUNDEEP
recursiongrammarcontext-free-grammar
gremo
gremo

Reputation: 48899

Find out the language generated, given a context-free grammar?

Should I manually apply the production rules to find out the language generated by this grammar? This is tedious, is there any trick/tip to speed up things?

G = {{S, B}, {a, b}, P, S}
P = {S -> aSa | aBa, B -> bB | b}

EDIT: I found Matajon's answer a good one, that is thinking about each language generated by non-terminal symbol and then combine them.

But I'm still stuck when I have to solve some complicated examples like this:

G = {{S, R, T}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, P, S}

P = {S -> A | AS | BR | CT,
     R -> AR | BT | C | CS,
     T -> AT | B | BS | CR,
     A -> 0 | 3 | 6 | 9,
     B -> 1 | 4 | 7,
     C -> 2 | 5 | 8}

Crazy, isn't it? Taken from past exams (programming languages course).

Upvotes: 1

Views: 3998

Answers (2)

Martin Jonáš
Martin Jonáš

Reputation: 2317

I don't know any general trick, but usually it helps to think about the language generated from each non-terminal.

In your example language generated from B is obviously L(B) = {b}^+. Then you think about S rules, using the first rule, you can generate sentencial forms {a^n.S.a^n | n >= 1}. If you use second rule on these sentencial forms or on S alone you can generate sentencial forms {a^n.B.a^n | n >= 1}.

Rest is pretty easy, you combine these two things and get L(G) = {a^n.b^+.a^n | n >= 1}

By the way, in the definition of grammar terminals and nonterminals are sets, not tuples. And third component is production rules, not start symbol. So you should write G = {{S, B}, {a, b}, P, S}.

Edit

Actually, there is a way to solve your second example without much thinking just by following something like a cookbook. Because, language generated by your second context-free grammar is in fact regular.

When you substitute rules for A, B and C to first three rules, you get

P' = {S -> 0 | 3 | 6 | 9 | 0S | 3S | 6S | 9S | 1R | 4R | 7R | 2T | 5T | 8T
     R -> 0R | 3R | 6R | 9R | 1T | 4T | 7T | 2 | 5 | 8 | 2S | 5S | 8S
     T -> 0T | 3T | 6T | 9T | 1 | 4 | 7 | 1S | 4S | 7S | 2R | 5R | 8R}

And P' is regular grammar. Because of that, you can convert it to nondeterministic finite automaton (there is really simple way, look for it) and then convert resulting NFA to the regular expression (this is not so simple but if you follow an algorithm and don't get lost, you should be ok). And it from regular expression it is easy to tell what language it describes.

Also, once you have NFA for this language you can look at it and determine what it does logically (it has something to do with counts of 1,4,7 and 2,5,8 in the word and mod 3 of their difference. Think it through, it is your homework, afterall :-) )

Of course, if you don't context-free grammar generating regular language you can't use this trick. There is no general way to tell what language the grammar generates (language equality problem for CFG's is undecideable), you have to think about every single example and look for similarities and patterns in it's logical structure.

Upvotes: 2

David Weiser
David Weiser

Reputation: 5195

I think you'll just need to apply the production rules.

Upvotes: 0

Related Questions