Thread: Grammar problem

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)^* ?

Originally Posted by Apprentice123

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 ?

Originally Posted by Apprentice123

OK. A derivation would:
SS
aSabSb
abSbabaSab
abEbabaEab
abbabaab

What language is that?

Compare what you just wrote with

SS
(S)[S]
([S])[(S)]
([])[()]

By the way it's not typical to write E inside the expression.

Originally Posted by Apprentice123

a^n b^n with n>=0 ?

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?

Originally Posted by Apprentice123

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 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?

Originally Posted by Apprentice123

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

???

Originally Posted by Apprentice123

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.

Thanks
What would a derivation more right and more left ?

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.

Thank you