Can You Minimize Production Rules in Chomsky Normal Form?

[twoski]

Homework Statement

Grammar 'G' is any context-free grammar without any λ productions or unit productions. Let k be the max number of symbols on the right side of any production in P. Prove that there's an equivalent grammar in Chomsky Normal Form with no more than (k − 1)|P| + |T| production rules.

The Attempt at a Solution

There isn't a single similar proof to this anywhere on the internet. There are a lot of basic proofs like proving any CFG can be converted to CNF but nothing this involved.

None of the proofs in my textbook involve minimizing production rules either. Productions in CNF can only be like A -> BC or A- > a, so this would be a factor. I don't know what else to do, should this proof be constructive or inductive?

 

[Greg Bernhardt]

Thanks for the post! Sorry you aren't generating responses at the moment. Do you have any further information, come to any new conclusions or is it possible to reword the post?