Simplification of Context Free Grammar ( Reduction of CFG) |Automata Theory
#cfg, simplificationofcfg, cfgsimplification, #csegatelecture, #thegatehub
Contact Datils (You can follow me at)
Instagram: / ahmadshoebkhan
LinkedIn: / ahmad-shoeb-957b6364
Facebook: / ahmadshoebkhan
Watch Complete Playlists:
Data Structures: • Introduction to Data Structures || Da...
Theory of Computation: • Introduction to Theory of Computation...
Compiler Design: • Ambiguous Grammar | Introduction to A...
This Lecture shows how to Simplify a given CFG and explains the Phases involved in the Reduction step.
As we have seen, various languages can efficiently be represented by a context-free grammar. All the grammar are not always optimized that means the grammar may consist of some extra symbols(non-terminal). Having extra symbols, unnecessary increase the length of grammar. Simplification of grammar means reduction of grammar by removing useless symbols. The properties of reduced grammar are given below:
Each variable (i.e. non-terminal) and each terminal of G appears in the derivation of some word in L.
There should not be any production as X → Y where X and Y are non-terminal.
If ε is not in the language L then there need not to be the production X → ε.
Removal of Useless Symbols: A symbol can be useless if it does not appear on the right-hand side of the production rule and does not take part in the derivation of any string. That symbol is known as a useless symbol. Similarly, a variable can be useless if it does not take part in the derivation of any string. That variable is known as a useless variable.
Elimination of ε Production: The productions of type S → ε are called ε productions. These type of productions can only be removed from those grammars that do not generate ε.
Step 1: First find out all nullable non-terminal variable which derives ε.
Step 2: For each production A → a, construct all production A → x, where x is obtained from a by removing one or more non-terminal from step 1.
Step 3: Now combine the result of step 2 with the original production and remove ε productions.
Removing Unit Productions: The unit productions are the productions in which one non-terminal gives another non-terminal. Use the following steps to remove unit production:
Step 1: To remove X → Y, add production X → a to the grammar rule whenever Y → a occurs in the grammar.
Step 2: Now delete X → Y from the grammar.
Step 3: Repeat step 1 and step 2 until all unit productions are removed.
cfg,context free grammar,simplification of context free grammar,context free grammar simplification,cfg simplification,simplification of cfg,cfg reduction,reduction of cfg,reduction context free grammar,context free grammar reduction,simplification context free grammar,phase in cfg,toc,cfg simplification in toc,simplification of cfg in toc,simplification of cfg in automata,gate cse lectures,gate lectures,thegatehub,gatehub,simplification of cfg e,simplification of cfg examples,cfg,context free grammar,cfg simplification,simplification of cfg,cfg reduction,reduction of cfg,reduction context free grammar,context free grammar reduction,context free grammar simplification,simplification context free grammar,phase in cfg,toc,toc lectures,automata,automata lectures,automata theory,automata theory lectures,gate cse lectures,gate lectures,computer science lectures,theory of computation,theory of computation lectures
Watch video Simplification of Context Free Grammar ( Reduction of CFG) |Automata Theory online without registration, duration hours minute second in high quality. This video was added by user THE GATEHUB 16 April 2020, don't forget to share it with your friends and acquaintances, it has been viewed on our site 77,89 once and liked it 1 thousand people.