Xoviabcs's video: Theory of Computation 18 Normal Forms Chomsky Normal Form

Unlimited Access to Best Programming Courses @ http://bit.ly/2lJYuGH Theory of Computation Normal Forms, Chomsky Normal Form. In this lecture we see a special form of CFGs known as Chomsky Normal Form. We also give a procedure to convert every CFG to an equivalent CFG in Chomsky Normal Form. There are many normal forms for CFGs. They are the forms of context free grammar which are broad enough so that any grammar has an equivalent normal form version. You may think of it as cleaning up the grammar. A context free grammar is in Chomsky normal form (CNF) if every production in the grammar is of any of form given below: A - BC A - a Where A, B and C are variables and a is a terminal symbol. Converting a context free grammar into Chomsky Normal Form can be done in four steps: - Eliminating ϵ-productions - Eliminating unit productions - 1Restricting the right side of the production to single terminals or strings of two or more variables - Finally reduce the long string of terminals at the right hand side to string of two terminals Theory of Computation (TOC) & Automata Theory NPTEL Gate Lectures @ https://goo.gl/cyoofd C Programming Tutorial/ Lectures/ Course with Data Structures & Algorithms @ https://goo.gl/K6VbgL Machine Learning Complete Tutorial/Lectures/Course from IIT (nptel) for GATE @ https://goo.gl/AurRXm Discrete Mathematics for Computer Science for GATE @ https://goo.gl/YJnA4B (IIT Lectures for GATE) Best Programming Courses @ http://bit.ly/2lJYuGH Operating Systems Lecture/Tutorials ravindrababu ravula from IIT for GATE CSE @ https://goo.gl/GMr3if MATLAB Tutorials for GATE @ https://goo.gl/EiPgCF ******************************* Recommended Books: https://amzn.to/2PTjhqc https://clnk.in/jxr2 *****************************