Question

Write down a Context Free Grammar with 8 productions including 4 variables and 3 terminals. i. Check whether the Context Free Grammar is ambiguous or not. Justify your answer with necessary example. ii. Finally, construct the reduced grammar corresponding to your generated grammar.

Answer 1

First thing before studying ambiguity is to learn about basics of CFGs.

Context Free Grammars(CFGs) are classified on the basis of

1.Number of Derivation trees

2.Number of strings

Number of Derivation trees furthur divides CFG  into 2 types:

1.Ambiguous grammars

2.Unambiguous grammars

Now i believe you must have got intuition behind ambiguity problem,

A CFG is said to ambiguous if there exists more than one derivation tree for the given input string i.e., more than one LeftMost Derivation Tree (LMDT) or RightMost Derivation Tree (RMDT).

So here is an example using 8 or more productions, 4 variables 3 terminals,

 Alphabet Set ∑ = { 0,...,9, +, *, . ,{,} }

A -> B     
A - > AA   
A -> A + A
A -> A * A
A -> {A}
B ->  0 | 1 | ... | 9

Now let us assume string to be derived using above grammer:

7 * 9 + 2

I) First leftmost derivation           II) Second  leftmost derivation
         A=>A*A                            A=>A+A
         =>B*A                             =>A*A+A
         =>7*A+A                           =>B*A+A
         =>7*B+A                           =>7*A+A
         =>7*9+A                           =>7*B+A
         =>7*9+B                           =>7*9+A
         =>7*9+2                           =>7*9+2

Now answer to your second question :

We have-

• Given grammar consists of the following operators-

+ , *,.

• Given grammar consists of the following operands-

0,1,2,...9

The priority order is-

(0,1,2...9) > * > . > +

where-

• . operator is left associative
• + operator is left associative

Using the precedence and associativity rules, we write the corresponding unambiguous grammar as-

A → A + B / B/{A}

B → B . C / C

C → C* / H

H → 0/1/2/3/4/5/6/7/8/9

Unambiguous Grammar

May be this precisely answers your question.