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.
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 with
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 like
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."
To tell the truth, I'm not sure of the best way to define the contextfree 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.
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
Thanks
What would a derivation more right and more left ?
Thank you