10 replies to this topic

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

[ferovac]

i'm just going to say no(let you deal with a problem a little bit more)

as you can see, you have aSa and bSb what means that you will always have a even number of "a" and "b" so a line like aaaaa isnt possible by the grammar but by your language it is

[bobdark]

ferovac said:

i'm just going to say no(let you deal with a problem a little bit more)

as you can see, you have aSa and bSb what means that you will always have a even number of "a" and "b" so a line like aaaaa isnt possible by the grammar but by your language it is

Wrong. You dont have to have an equal number of a's and b's in the word. Your saying would have been correct if instead S->aSa|bSb it were something like S->aSb|bSa, i.e. each rule would contribute equal number of a's and b's to the word.

Regarding the question though, there's a directing question:
if there was no rule S->SS, what would the language be? Clue word: symmetry.

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

[bobdark]

In my example the language would be :
WWr, where Wr is W reversed.
If there is some word in L such that L=L(G), that there is more than 1 possible derivation for that word, the grammar is ambigous

[abzero]

Just use the grammar to get some examples and see what it produces.

A grammar is ambiguous if there is a situation in which it's possible that two productions could be used.
So for a LL(1) grammar, imagine these productions:

S->ab
S->ac
S->b

if you have the string ab, you can't with a look ahead of 1 select between the ab&ac productions. The grammar is ambigious.

[Apprentice123]

Thanks
So this grammar is ambiguous
We can:

S => aSa => a aSa a => aaaa
S => SS => aSa aSa => aaaa


How is a tree derivation ?

[bobdark]

abzero said:

Just use the grammar to get some examples and see what it produces.

A grammar is ambiguous if there is a situation in which it's possible that two productions could be used.
So for a LL(1) grammar, imagine these productions:

S->ab
S->ac
S->b

if you have the string ab, you can't with a look ahead of 1 select between the ab&ac productions. The grammar is ambigious.

Wrong. This is not an ambigous grammar. It is for example in LL(2).
An ambigous grammar is not in any parsing class, because no matter what lookahead you got or whatever, if there are two different derivations for a word, you can't decide which one is it.
This for example is an ambigous grammar:
S->A|B
A->a
B->a
And yes the grammar S->SS|aSa|bSb|E is ambigous

[Apprentice123]

Thank you
in the grammar S->SS|aSa|bSb|E

The tree derivation of the word aabbaaaa is:

               S
            /  |  \
          a    S     a  
             /    \
           S       S
        /  | \    / | \
      a   S  a  a  S a
        /  | \        |
      b   S  b      E
           |
           E

?

[ferovac]

bobdark said:

Wrong. You dont have to have an equal number of a's and b's in the word. Your saying would have been correct if instead S->aSa|bSb it were something like S->aSb|bSa, i.e. each rule would contribute equal number of a's and b's to the word.

Regarding the question though, there's a directing question:
if there was no rule S->SS, what would the language be? Clue word: symmetry.

i meant even number of "a" and a even number of "b" so "aaaaa" wont work and "aa" , "aabb", "abbbba" will work

[bobmacans]

It nice to learn that.