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---->AA---->BB---->a/b/cresultant grammar ,S---->a/b/cSo , it is O(m) time .Can you explain in formal way, please?
Does removal of unit production from the grammar may increase number of total production?
context free;formal grammars;normal forms
Hint: Consider the grammar$$S \to \overbrace{X\cdots X}^{\text{$n$ times}} \\ X\to a|b$$What happens when you remove unit productions?