1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Chomsky Normal Form Proof

  1. Nov 7, 2014 #1
    1. The problem statement, all variables and given/known data

    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.

    3. 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 dunno what else to do, should this proof be constructive or inductive?
  2. jcsd
  3. Nov 12, 2014 #2
    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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted