# Does removal of unit production from the grammar may increase number of total production?

There are m variable 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$)

(c) O($k^m$)

(d) O($2^m$)

My attempt:

He asked about number of total production remains in the minimized grammar , so , if the there is no null production , it is advantage , as you know when we convert a grammar without null production , generally , removal of all production introduces new production in the resultant grammar (it can be upto set of all subset of given max RHS number of variable , so exponetial ) .

But , in given grammar , you don't have null production , so you are removing only unit production (i.e. A--->B type productions ) , 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 .

Can you explain in formal way, please?

• Hint: there is more than one correct answer. (What is $k$?) – Raphael Oct 2 '15 at 19:59
• $k$ is constant – ً ً Oct 3 '15 at 6:02
• Then all answers are correct (if $k\geq 2$). – Raphael Oct 3 '15 at 10:44

Hint: Consider the grammar $$S \to \overbrace{X\cdots X}^{\text{n times}} \\ X\to a|b$$ What happens when you remove unit productions?
• No, the minimized grammar is rather different from $S\to a|b$. – Yuval Filmus Sep 3 '15 at 6:23
• If I am consider given grammar as S---->XXXXX....n-times, and X---->a|b , then minimized grammar should be O($2^n$) productions . Sir, Again I have two queris (1) Is the production S----->XXXXX... unit production ? (2) If , there was X---->a|b|....m-times , then the minimized productions O($m^n$) ? Am I rt ? – ً ً Sep 3 '15 at 6:51