patternMinor
Finding the language generated by a context-free grammar
Viewed 0 times
generatedthefreelanguagegrammarfindingcontext
Problem
This is a question from the Dragon book (I apologize for translation mistakes, I don´t have the English version on hand):
What language is generated by this grammar?
$S \rightarrow a S b S \mid b S a S \mid \epsilon$
I don't know what I'm supposed to do here. The definition in the book about languages says this (and that's pretty much it in the chapter):
a language is the set of all words that can be produced by any parse
tree.
So, if I want to make "any" parse tree out of this grammar, I can recursively keep building it, using just the first two rules. I searched a bit and got the impression that every rule has to be used once, but I'm not sure. It would be very helpful if someone were able to provide some tips on solving these sorts of problems.
What language is generated by this grammar?
$S \rightarrow a S b S \mid b S a S \mid \epsilon$
I don't know what I'm supposed to do here. The definition in the book about languages says this (and that's pretty much it in the chapter):
a language is the set of all words that can be produced by any parse
tree.
So, if I want to make "any" parse tree out of this grammar, I can recursively keep building it, using just the first two rules. I searched a bit and got the impression that every rule has to be used once, but I'm not sure. It would be very helpful if someone were able to provide some tips on solving these sorts of problems.
Solution
Hint: What can you say about the number of $a$s and $b$s in the produced words?
It would be very helpful if someone were able to provide some tips on
solving these sorts of problems.
There is no one-size-fits-all recipe here. It is undecidable in general, whether two CFGs produce the same language or two CFLs are the same language. A useful method is trying to notice the properties which remain invariant during the productions.
It would be very helpful if someone were able to provide some tips on
solving these sorts of problems.
There is no one-size-fits-all recipe here. It is undecidable in general, whether two CFGs produce the same language or two CFLs are the same language. A useful method is trying to notice the properties which remain invariant during the productions.
Context
StackExchange Computer Science Q#10605, answer score: 7
Revisions (0)
No revisions yet.