{"id":6549,"date":"2026-03-17T11:35:30","date_gmt":"2026-03-17T06:05:30","guid":{"rendered":"https:\/\/study.madeeasy.in\/?p=6549"},"modified":"2026-03-30T17:05:30","modified_gmt":"2026-03-30T11:35:30","slug":"chomsky-normal-form-cnf","status":"publish","type":"post","link":"https:\/\/www.madeeasy.in\/study\/cs-it\/chomsky-normal-form-cnf","title":{"rendered":"Chomsky Normal Form (CNF)"},"content":{"rendered":"<h2 style=\"text-align: center;\">Chomsky Normal Form (CNF) in Compiler Design<\/h2>\n<ul>\n<li style=\"text-align: justify;\">Any context free grammar G = (V, T, S, P) with \u03bb \u2209 L(G) has an equivalent grammar in Chomsky Normal Form.<\/li>\n<li style=\"text-align: justify;\">There are two types of productions in CNF grammar:<\/li>\n<\/ul>\n<p style=\"text-align: center;\">&lt;variable&gt;\u2192 &lt;terminal&gt;<\/p>\n<p style=\"text-align: center;\">&lt;variable&gt;\u2192 &lt;variable&gt;&lt;variable&gt;<\/p>\n<ul style=\"text-align: justify;\">\n<li>In RHS of every production of the Chomsky Normal Form grammar contain only two non terminals or a single terminal.<\/li>\n<\/ul>\n<p style=\"text-align: center;\">A \u2192 BC<br \/>\nA \u2192 a<\/p>\n<ul style=\"text-align: justify;\">\n<li>CNF is also called as binary standard form.<\/li>\n<li>The number of productions are required for generating x-length string from the given CNF context<br \/>\nfree grammar is: (2x \u2013 1)<\/li>\n<\/ul>\n<p style=\"text-align: center;\">Example: Consider a context free grammar in Chomsky\u2019s Normal Form<\/p>\n<p style=\"text-align: center;\">S \u2192 AB<br \/>\nA \u2192 a<br \/>\nB \u2192 b<\/p>\n<p style=\"text-align: center;\">Number of productions used = 3 i.e. 2x \u2013 1 where x = length of string.<\/p>\n<ul style=\"text-align: justify;\">\n<li>Let \u2018G\u2019 be the given Chomsky Normal Form grammar and \u2018T \u2019 be the derivation tree for some string \u2018x\u2019 in G. If the length<br \/>\nof the longest path is equal to k then yield length \u2264 2k \u2013 1.<\/li>\n<li>For the generation of \u2018l\u2019 length yield, the minimum height of the derivation tree for the given CNF<br \/>\ncontext free grammar<\/li>\n<li>Let h be the minimum height of the derivation tree, which gives yield of length \u2018l\u2019.<\/li>\n<\/ul>\n<p style=\"text-align: center;\">l = 2h \u2013 1 \u21d2 h \u2013 1 = log2 l \u21d2 h = log2 l + 1.<\/p>\n<ul>\n<li style=\"text-align: justify;\">Let \u2018G\u2019 be the given CFG without null productions and unit productions and \u2018k\u2019 be the maximum<br \/>\nnumber of symbols on the right hand side of any production.<\/li>\n<li style=\"text-align: justify;\">Then the equivalent CNF (Chomsky Normal Form) contain a maximum of: (k \u2013 1)|P| + |T| productions.<br \/>\nwhere, |P| = the number of productions in \u2018G\u2019, |T| = the number of terminals, k = maximum number of symbols on right hand side.<\/li>\n<\/ul>\n<p style=\"text-align: center;\"><a class=\"btn btn-danger\" role=\"button\" href=\"https:\/\/study.madeeasy.in\/cs-it\/leftmost-and-rightmost-derivations\" target=\"_blank\" rel=\"noopener\">&lt;&lt; Previous<\/a> | <a class=\"btn btn-success\" role=\"button\" href=\"https:\/\/study.madeeasy.in\/cs-it\/greibach-normal-form-gnf\" target=\"_blank\" rel=\"noopener\"> Next &gt;&gt;<\/a><br \/>\n<strong> Must Read: <\/strong> <a href=\"https:\/\/study.madeeasy.in\/cs-it\/what-is-theory-of-computation\" target=\"_blank\" rel=\"noopener\"><strong>What is Theory of Computation?<\/strong><\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Chomsky Normal Form (CNF) in Compiler Design Any context free grammar G = (V, T, S, P) with \u03bb \u2209<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,1930],"tags":[],"class_list":["post-6549","post","type-post","status-publish","format-standard","hentry","category-cs-it","category-computation"],"_links":{"self":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/posts\/6549","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/comments?post=6549"}],"version-history":[{"count":0,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/posts\/6549\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/media?parent=6549"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/categories?post=6549"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/tags?post=6549"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}