If there is no \u2208 in the language then there should not be any product that tends to \u2208.<\/li>\n<\/ol>\n1. Eliminating Useless Symbols<\/h4>\n
We refer to a symbol or variable as useless if it doesn\u2019t appear on the right side of any production rule of the grammar. They are useless even if it doesn\u2019t contribute in deriving any string.<\/p>\n
Example:<\/em><\/p>\nS -> aB | adA |abT
\nA -> aA
\nB -> ab|d
\nC -> ab<\/div>\n
In the above grammar, we cannot use the variable \u2018C\u2019 in deriving any string. As we can not reach variable ‘C’ from the starting symbol T. So we can <\/span>eliminate<\/span><\/span> the production C -> ab.<\/span><\/p>\nObserve that the variable A in the grammar above is useless. As there is no way to terminate the symbol ‘A’. Thus, it will never produce a string. So, we must eliminate production A -> aA such that no variable should lead to a string consisting of variable A.<\/p>\n
So, the modified grammar is:<\/p>\n
S -> aB | abT
\nB -> ab|d<\/div>\n
2. Eliminate Production with \u2208<\/h4>\n
To simplify CFG we need to eliminate the production such as A -> \u2208 also referred to as null productions. We can eliminate such production if the grammar does not generate an empty string. It is possible for a grammar to contain null production and yet does not produce an empty string.<\/p>\n
Steps to remove null productions:<\/em><\/p>\n\n- Identify all the non-terminals that derive \u2208.<\/li>\n
- Construct all the production for the non-terminals (identified in step 1) by substituting \u2208.<\/li>\n
- Now integrate the results of step 2 with original grammar. And eliminate \u2208 from the production.<\/li>\n<\/ol>\n
Example:<\/em> Consider the grammar<\/p>\nS\u00a0\u2192\u00a0ABA
\nA \u2192 aA | \u2208
\nB\u00a0\u2192\u00a0bB\u00a0|\u00a0\u2208<\/div>\n
From the productions above we have to eliminate A -> \u2208 and B -> \u2208 such that the meaning of the original CFG is still preserved. Let us take the first production with the starting symbol S:<\/p>\n
S -> ABA<\/div>\n
First, we will substitute A -> \u2208 at first A of the production body. It results in:<\/p>\n
S -> BA<\/div>\n
Now, substitute A -> \u2208 at last A of the production it would result in:<\/p>\n
S -> AB<\/div>\n
Now if we substitute B -> \u2208<\/p>\n
S -> AA<\/div>\n
If A -> \u2208 and B -> \u2208 then<\/p>\n
S-> A<\/div>\n
If both As are replaced by \u2208<\/p>\n
S -> B<\/div>\n
Now we will integrate the result with the original production rule of variable S.<\/p>\n
S -> AB| BA | AA | A | B<\/div>\n
Similarly, we will replace \u2208 in the production:<\/p>\n
A -> aA<\/div>\n
If A -> \u2208 then<\/p>\n
A -> a<\/div>\n
So, the original production we will appear as<\/p>\n
A -> aA | a<\/div>\n
Similarly, for B -> bB<\/p>\n
B -> bB | b<\/div>\n
At last the grammar after eliminating \u2208 from the original grammar it appears as:<\/p>\n
S -> AB| BA | AA | A | B
\nA -> aA | a
\nB -> bB | b<\/div>\n
3. Eliminating Unit Productions<\/h4>\n
In a unit production, a non-terminal tends to another non-terminal such as A -> B.<\/p>\n
Example:<\/em><\/p>\nS -> Aa | B
\nA -> b | B
\nB -> A | a<\/div>\n
The unit productions that we have in the original grammar are:<\/p>\n
S -> B
\nA -> B
\nB -> A<\/div>\n
To eliminate unit productions, replace the non-terminal at the right side of the production with terminals. It will result in:<\/p>\n
S -> b | a \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0(Since S -> B where B -> A|a & A -> b)
\nA -> a
\nB -> b<\/div>\n
Now integrate the improvised unit production to the original grammar.<\/p>\n
S -> Aa | a | b
\nA -> b | a
\nB -> b | a<\/div>\n
The symbol ‘B’ in the above grammar is useless. Because, there is no way to reach symbol ‘B’ from the starting symbol S. So, further we will eliminate symbol B.
\nThus, the resultant CFG would be:<\/p>\n
S -> Aa | a | b
\nA -> b | a<\/div>\n
<\/a><\/p>\nApplications of CFG<\/h3>\n\n- As CFG can efficiently describe a programming language. We can turn context-free grammar into a parser.<\/li>\n
- CFG is helpful in describing the document type definition DTD in XML.<\/li>\n<\/ul>\n
So, this is all about the context-free grammar CFG. We have learnt about CFG, ambiguous CFG, simplification of CFG and applications of CFG.<\/p>\n","protected":false},"excerpt":{"rendered":"
Context-free grammar (CFG) is a set of production rules that generates context-free language. In this context, we will be learning about the ambiguity in the CFG, its simplification, and its applications. Content: Context-free Grammar What is Context-free Grammar? Notational Conventions of CFG Ambiguity in Context-free Grammar Simplification of Context-free Grammar Applications of Context-free Grammar What […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_genesis_hide_title":false,"_genesis_hide_breadcrumbs":false,"_genesis_hide_singular_image":false,"_genesis_hide_footer_widgets":false,"_genesis_custom_body_class":"","_genesis_custom_post_class":"","_genesis_layout":"","footnotes":""},"categories":[13],"tags":[],"class_list":{"0":"post-3235","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-compiler-design","7":"entry"},"yoast_head":"\n
What is Context-free Grammar: Definition, Example, Simplification, & Applications - Binary Terms<\/title>\n<meta name=\"description\" content=\"Context-free grammar (CFG) is a set of production rules that helps in generating context-free language.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/binaryterms.com\/context-free-grammar.html\" \/>\n<meta property=\"og:locale\" content=\"en_GB\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"What is Context-free Grammar: Definition, Example, Simplification, & Applications - Binary Terms\" \/>\n<meta property=\"og:description\" content=\"Context-free grammar (CFG) is a set of production rules that helps in generating context-free language.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/binaryterms.com\/context-free-grammar.html\" \/>\n<meta property=\"og:site_name\" content=\"Binary Terms\" \/>\n<meta property=\"article:published_time\" content=\"2021-12-30T12:00:06+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-01-10T05:37:31+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Ambiguous-sentence-of-context-free-grammar-1-1.jpg\" \/>\n<meta name=\"author\" content=\"Neha T\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Neha T\" \/>\n\t<meta name=\"twitter:label2\" content=\"Estimated reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"8 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/binaryterms.com\/context-free-grammar.html#article\",\"isPartOf\":{\"@id\":\"https:\/\/binaryterms.com\/context-free-grammar.html\"},\"author\":{\"name\":\"Neha T\",\"@id\":\"https:\/\/binaryterms.com\/#\/schema\/person\/e495f1d57f5c0a4c521cc3dba95661fe\"},\"headline\":\"Context-free Grammar\",\"datePublished\":\"2021-12-30T12:00:06+00:00\",\"dateModified\":\"2022-01-10T05:37:31+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/binaryterms.com\/context-free-grammar.html\"},\"wordCount\":1527,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\/\/binaryterms.com\/#organization\"},\"image\":{\"@id\":\"https:\/\/binaryterms.com\/context-free-grammar.html#primaryimage\"},\"thumbnailUrl\":\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Ambiguous-sentence-of-context-free-grammar-1-1.jpg\",\"articleSection\":[\"Compiler Design\"],\"inLanguage\":\"en-GB\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/binaryterms.com\/context-free-grammar.html#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/binaryterms.com\/context-free-grammar.html\",\"url\":\"https:\/\/binaryterms.com\/context-free-grammar.html\",\"name\":\"What is Context-free Grammar: Definition, Example, Simplification, & Applications - Binary Terms\",\"isPartOf\":{\"@id\":\"https:\/\/binaryterms.com\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/binaryterms.com\/context-free-grammar.html#primaryimage\"},\"image\":{\"@id\":\"https:\/\/binaryterms.com\/context-free-grammar.html#primaryimage\"},\"thumbnailUrl\":\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Ambiguous-sentence-of-context-free-grammar-1-1.jpg\",\"datePublished\":\"2021-12-30T12:00:06+00:00\",\"dateModified\":\"2022-01-10T05:37:31+00:00\",\"description\":\"Context-free grammar (CFG) is a set of production rules that helps in generating context-free language.\",\"breadcrumb\":{\"@id\":\"https:\/\/binaryterms.com\/context-free-grammar.html#breadcrumb\"},\"inLanguage\":\"en-GB\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/binaryterms.com\/context-free-grammar.html\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-GB\",\"@id\":\"https:\/\/binaryterms.com\/context-free-grammar.html#primaryimage\",\"url\":\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Ambiguous-sentence-of-context-free-grammar-1-1.jpg\",\"contentUrl\":\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Ambiguous-sentence-of-context-free-grammar-1-1.jpg\",\"width\":490,\"height\":204,\"caption\":\"Ambiguous sentence of context free grammar 1-1\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/binaryterms.com\/context-free-grammar.html#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/binaryterms.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Context-free Grammar\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/binaryterms.com\/#website\",\"url\":\"https:\/\/binaryterms.com\/\",\"name\":\"Binary Terms\",\"description\":\"The Computer Science & IT Guide\",\"publisher\":{\"@id\":\"https:\/\/binaryterms.com\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/binaryterms.com\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-GB\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/binaryterms.com\/#organization\",\"name\":\"Binary Terms\",\"url\":\"https:\/\/binaryterms.com\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-GB\",\"@id\":\"https:\/\/binaryterms.com\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/binaryterms.com\/wp-content\/uploads\/2020\/05\/binary-terms-logo1.png\",\"contentUrl\":\"https:\/\/binaryterms.com\/wp-content\/uploads\/2020\/05\/binary-terms-logo1.png\",\"width\":400,\"height\":63,\"caption\":\"Binary Terms\"},\"image\":{\"@id\":\"https:\/\/binaryterms.com\/#\/schema\/logo\/image\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\/\/binaryterms.com\/#\/schema\/person\/e495f1d57f5c0a4c521cc3dba95661fe\",\"name\":\"Neha T\",\"url\":\"https:\/\/binaryterms.com\/author\/author\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"What is Context-free Grammar: Definition, Example, Simplification, & Applications - Binary Terms","description":"Context-free grammar (CFG) is a set of production rules that helps in generating context-free language.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/binaryterms.com\/context-free-grammar.html","og_locale":"en_GB","og_type":"article","og_title":"What is Context-free Grammar: Definition, Example, Simplification, & Applications - Binary Terms","og_description":"Context-free grammar (CFG) is a set of production rules that helps in generating context-free language.","og_url":"https:\/\/binaryterms.com\/context-free-grammar.html","og_site_name":"Binary Terms","article_published_time":"2021-12-30T12:00:06+00:00","article_modified_time":"2022-01-10T05:37:31+00:00","og_image":[{"url":"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Ambiguous-sentence-of-context-free-grammar-1-1.jpg","type":"","width":"","height":""}],"author":"Neha T","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Neha T","Estimated reading time":"8 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/binaryterms.com\/context-free-grammar.html#article","isPartOf":{"@id":"https:\/\/binaryterms.com\/context-free-grammar.html"},"author":{"name":"Neha T","@id":"https:\/\/binaryterms.com\/#\/schema\/person\/e495f1d57f5c0a4c521cc3dba95661fe"},"headline":"Context-free Grammar","datePublished":"2021-12-30T12:00:06+00:00","dateModified":"2022-01-10T05:37:31+00:00","mainEntityOfPage":{"@id":"https:\/\/binaryterms.com\/context-free-grammar.html"},"wordCount":1527,"commentCount":0,"publisher":{"@id":"https:\/\/binaryterms.com\/#organization"},"image":{"@id":"https:\/\/binaryterms.com\/context-free-grammar.html#primaryimage"},"thumbnailUrl":"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Ambiguous-sentence-of-context-free-grammar-1-1.jpg","articleSection":["Compiler Design"],"inLanguage":"en-GB","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/binaryterms.com\/context-free-grammar.html#respond"]}]},{"@type":"WebPage","@id":"https:\/\/binaryterms.com\/context-free-grammar.html","url":"https:\/\/binaryterms.com\/context-free-grammar.html","name":"What is Context-free Grammar: Definition, Example, Simplification, & Applications - Binary Terms","isPartOf":{"@id":"https:\/\/binaryterms.com\/#website"},"primaryImageOfPage":{"@id":"https:\/\/binaryterms.com\/context-free-grammar.html#primaryimage"},"image":{"@id":"https:\/\/binaryterms.com\/context-free-grammar.html#primaryimage"},"thumbnailUrl":"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Ambiguous-sentence-of-context-free-grammar-1-1.jpg","datePublished":"2021-12-30T12:00:06+00:00","dateModified":"2022-01-10T05:37:31+00:00","description":"Context-free grammar (CFG) is a set of production rules that helps in generating context-free language.","breadcrumb":{"@id":"https:\/\/binaryterms.com\/context-free-grammar.html#breadcrumb"},"inLanguage":"en-GB","potentialAction":[{"@type":"ReadAction","target":["https:\/\/binaryterms.com\/context-free-grammar.html"]}]},{"@type":"ImageObject","inLanguage":"en-GB","@id":"https:\/\/binaryterms.com\/context-free-grammar.html#primaryimage","url":"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Ambiguous-sentence-of-context-free-grammar-1-1.jpg","contentUrl":"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Ambiguous-sentence-of-context-free-grammar-1-1.jpg","width":490,"height":204,"caption":"Ambiguous sentence of context free grammar 1-1"},{"@type":"BreadcrumbList","@id":"https:\/\/binaryterms.com\/context-free-grammar.html#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/binaryterms.com\/"},{"@type":"ListItem","position":2,"name":"Context-free Grammar"}]},{"@type":"WebSite","@id":"https:\/\/binaryterms.com\/#website","url":"https:\/\/binaryterms.com\/","name":"Binary Terms","description":"The Computer Science & IT Guide","publisher":{"@id":"https:\/\/binaryterms.com\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/binaryterms.com\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-GB"},{"@type":"Organization","@id":"https:\/\/binaryterms.com\/#organization","name":"Binary Terms","url":"https:\/\/binaryterms.com\/","logo":{"@type":"ImageObject","inLanguage":"en-GB","@id":"https:\/\/binaryterms.com\/#\/schema\/logo\/image\/","url":"https:\/\/binaryterms.com\/wp-content\/uploads\/2020\/05\/binary-terms-logo1.png","contentUrl":"https:\/\/binaryterms.com\/wp-content\/uploads\/2020\/05\/binary-terms-logo1.png","width":400,"height":63,"caption":"Binary Terms"},"image":{"@id":"https:\/\/binaryterms.com\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/binaryterms.com\/#\/schema\/person\/e495f1d57f5c0a4c521cc3dba95661fe","name":"Neha T","url":"https:\/\/binaryterms.com\/author\/author"}]}},"_links":{"self":[{"href":"https:\/\/binaryterms.com\/wp-json\/wp\/v2\/posts\/3235","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/binaryterms.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/binaryterms.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/binaryterms.com\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/binaryterms.com\/wp-json\/wp\/v2\/comments?post=3235"}],"version-history":[{"count":21,"href":"https:\/\/binaryterms.com\/wp-json\/wp\/v2\/posts\/3235\/revisions"}],"predecessor-version":[{"id":3275,"href":"https:\/\/binaryterms.com\/wp-json\/wp\/v2\/posts\/3235\/revisions\/3275"}],"wp:attachment":[{"href":"https:\/\/binaryterms.com\/wp-json\/wp\/v2\/media?parent=3235"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/binaryterms.com\/wp-json\/wp\/v2\/categories?post=3235"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/binaryterms.com\/wp-json\/wp\/v2\/tags?post=3235"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![\"Ambiguous](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Ambiguous-sentence-of-context-free-grammar-1-1.jpg\")
![\"Ambiguous](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Ambiguous-sentence-of-context-free-grammar-1-2.jpg\")
<\/p>\n![\"Simplification](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Simplification-of-CFG.jpg\")
<\/p>\n