{"id":6552,"date":"2026-03-18T11:28:12","date_gmt":"2026-03-18T05:58:12","guid":{"rendered":"https:\/\/study.madeeasy.in\/?p=6552"},"modified":"2026-03-30T17:07:30","modified_gmt":"2026-03-30T11:37:30","slug":"greibach-normal-form-gnf","status":"publish","type":"post","link":"https:\/\/www.madeeasy.in\/study\/cs-it\/greibach-normal-form-gnf","title":{"rendered":"Greibach Normal Form (GNF)"},"content":{"rendered":"<h2 style=\"text-align: center;\">Greibach Normal Form (GNF) in Compiler Design<\/h2>\n<p style=\"text-align: justify;\">A CFG G = (V, T, P, S) is in Greibach Normal Form (GNF) if its all productions are of type A \u2192 a\u03b1, where<br \/>\n\u03b1 \u2208 V* (string of variables including null string) and a is single terminal (a \u2208 T).<\/p>\n<ul>\n<li style=\"text-align: justify;\">Every CFG production of GNF grammar contains a single terminal (a) followed by any sequence of<br \/>\nnon-terminals (\u03b1). i.e., A \u2192 a\u03b1<\/li>\n<li style=\"text-align: justify;\">\u00a0Every CFL L without null string (\u03b5) can be generated by GNF grammar has productions are of type<br \/>\nA \u2192 a\u03b1, where \u03b1 \u2208 V* and a \u2208 T.<\/li>\n<li style=\"text-align: justify;\">No CNF or no GNF context free grammar generates the null string. Hence for \u03b5-free CFG\u2019s only we can construct an equivalent CNF or an equivalent GNF.<\/li>\n<li style=\"text-align: justify;\">In GNF context free grammar, the restrictions only on the positions, but not on length of right side of a production.<\/li>\n<li style=\"text-align: justify;\">The number of productions required to generate the x-length string from the given GNF-context free grammar is: |x|<strong>Example:<\/strong> To produce a string \u201cab\u201d.<br \/>\nNumber of productions = length of the string = |ab| = 2.<br \/>\nThe productions are: S \u2192 aB and B \u2192 b<\/li>\n<\/ul>\n<p style=\"text-align: center;\"><a class=\"btn btn-danger\" role=\"button\" href=\"https:\/\/study.madeeasy.in\/cs-it\/chomsky-normal-form-cnf\" target=\"_blank\" rel=\"noopener\">&lt;&lt; Previous<\/a> | <a class=\"btn btn-success\" role=\"button\" href=\"https:\/\/study.madeeasy.in\/cs-it\/turing-machine\" 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>Greibach Normal Form (GNF) in Compiler Design A CFG G = (V, T, P, S) is in Greibach Normal Form<\/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":[1944],"class_list":["post-6552","post","type-post","status-publish","format-standard","hentry","category-cs-it","category-computation","tag-greibach-normal-form"],"_links":{"self":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/posts\/6552","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=6552"}],"version-history":[{"count":0,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/posts\/6552\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/media?parent=6552"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/categories?post=6552"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/tags?post=6552"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}