Removing unit productions

Question

There are m variables in a grammar. The number of productions after removal of unit productions in the worst case is ,(Assume there are no null productions)

(a) O(m)
(b) O(m^2)m2m2)

(c) O(k^m)kk^mkm)

(d) O(2^m)2

Answer 1

Ans (a)

m variable can produce maximum m+1 productions

Comments

The worst case scenario has to be considered. That would be definitely more than m+1 productions after removing unit productions ( does not change the number of productions ) since we can have more than one production for a given variable.

Eg:

S -> ABC

A -> B | C

B -> C | A

C -> A | B

We have 3 variables A,B,C and there are 2*m productions just considering A,B and C.

---

resultant grammar maximum 'm' production , where m is number of variable . example :- S---->A A---->B B---->a/b/c resultant grammar , S---->a/b/c So , it is O(m) time .