Given the grammar G=({S},{a,b},P,S) where:
S -> SS | aSa | bSb | E
E is empty
What is the language generated ?
is (a+b)^* ?
Printable View
Given the grammar G=({S},{a,b},P,S) where:
S -> SS | aSa | bSb | E
E is empty
What is the language generated ?
is (a+b)^* ?
I believe the language generated is equivalent to this, except that () is replaced by aa and [] by bb.Quote:
Originally Posted by Apprentice123
By the way, I don't know what you meant by (a+b)^* because I think the "+" operator is only defined when it is a superscript, as in a^+, meaning aa^*.
OK. A derivation would:
SS
aSabSb
abSbabaSab
abEbabaEab
abbabaab
What language is that?
a^n b^n with n>=0 ?
Compare what you just wrote withQuote:
Originally Posted by Apprentice123
SS
(S)[S]
([S])[(S)]
([])[()]
By the way it's not typical to write E inside the expression.
No, because you just produced a string that is not in that language. The language a^n b^n with n>=0 has strings likeQuote:
Originally Posted by Apprentice123
E
ab
aabb
aaabbb
etc.
I think the language is: number pair of a's and b's (considering 0 as pair). Is that it?
How do I know if this grammar is ambiguous?
Well you'd have to mention "nested" in there somewhere, and perhaps "matching."Quote:
Originally Posted by Apprentice123
To tell the truth, I'm not sure of the best way to define the context-free language in English or in symbols. I would probably end up taking the "easy way out" by describing the language as: the language obtained by taking the language that contains all strings consisting of two different kinds of matching nested parentheses () and [], and replacing ( with a and ) with a and [ with b and ] with b.
There's probably a better way to say this. But if it were a homework assignment, I would think of the easy way out as "good enough" and wait for the professor's/grader's feedback.. that's just me.
Thanks. How do I know if this grammar is ambiguous?
Definition of ambiguous grammar: there exists a string that can be generated by the grammar in more than one way.Quote:
Originally Posted by Apprentice123
I think we can use trivial examples here
S -> E
S -> SS -> E
Or slightly less trivial
S -> SS -> aSaaSa -> aaaa
S -> aSa -> aaSaa -> aaaa
(So the grammar is in fact ambiguous.)
Thanks
The tree derivation of the word aabbaaaa is:
???Code:S
/ | \
a S a
/ \
S S
/ | \ / | \
a S a a S a
/ | \ |
b S b E
|
E
Looks good to me. Keep in mind that this is not the only possible way to generate the string.Quote:
Originally Posted by Apprentice123
Thanks
What would a derivation more right and more left ?
More right and more left? You mean the with the balance of the tree shifted, so to speak? Just play around, you'll find something.Quote:
Originally Posted by Apprentice123
Thank you