Ambiguity Grammar

Ambiguity Grammar
If , for all x belonged to L(G) ,any derivation of x yields the same derivation tree ,the CFG ,G,is said "unambiguous" .If on the other hand , two or more distinct derivation trees exist for some x belong to L(G) ,G is said to be "ambiguous" .For example the following grammar is ambiguous :
S SbS | SdS |a
To derive abada ,we have two derivation trees
1) S SbS abS abSdS abada
2) S SdS SbSdS abSdS abada

Example :
The following grammar is unambiguous :
S AB
A aA |a
B bB |b

There are some alternative derivations of a3b2



Equivalent Grammar

Some times ,may be that two different grammars G1 and G2 generate the same language L(G)=L(G2).
In that case the grammars are said to be equivalent .

Example 1:

Let G1 with production :

S A | B
A aA | a
B bB | b

The grammar equivalent to G1 is G2 with production :



S aA | bB |a|b
A aA |a
B bB | b


Because the G1 and G2 generate the same language .




H.w//

Find the equivalent to G1 with production :

S 0A
A dA | dB
B bB | b