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?

  • $\begingroup$ Hint: there is more than one correct answer. (What is $k$?) $\endgroup$ – Raphael Oct 2 '15 at 19:59
  • $\begingroup$ $k$ is constant $\endgroup$ – ً ً Oct 3 '15 at 6:02
  • 1
    $\begingroup$ Then all answers are correct (if $k\geq 2$). $\endgroup$ – 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?

| cite | improve this answer | |
  • $\begingroup$ Resultant grammar will be S--->a|b|..|a|b....2n-times , so total number of productions are O(2n) , minimized grammar is S--->a|b . rt , sir ? $\endgroup$ – ً ً Sep 3 '15 at 6:09
  • 1
    $\begingroup$ No, the minimized grammar is rather different from $S\to a|b$. $\endgroup$ – Yuval Filmus Sep 3 '15 at 6:23
  • $\begingroup$ 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 ? $\endgroup$ – ً ً Sep 3 '15 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.