0
$\begingroup$

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?

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

1 Answer 1

3
$\begingroup$

Hint: Consider the grammar $$S \to \overbrace{X\cdots X}^{\text{$n$ times}} \\ X\to a|b$$ What happens when you remove unit productions?

$\endgroup$
3
  • $\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, 2015 at 6:09
  • 1
    $\begingroup$ No, the minimized grammar is rather different from $S\to a|b$. $\endgroup$ Sep 3, 2015 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, 2015 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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