Chomsky Normal Form (CNF) and Conversion of Context-Free Grammars (CFG)

Chomsky Normal Form | CNF | Normal form of CFG | Conversion of CFG to CNF | TOC | FLAT | Automata There are two normal form of CFG - 1. Chomsky Normal Form (CNF) 2. Greibach Normal Form (GNF) 1. Chomsky Normal Form (CNF): A grammar is said to be in CNF, if the production of form 𝑨 → 𝑩𝑪 𝑜𝑟 𝑨 → 𝒂 where A,B and C are non-terminals and a is terminal In order to convert CFG into CNF following steps should be followed- 1. Removing null productions 2. Removing Unit productions 3. Obtain grammar in CNF Example: Obtain equivalent CNF form for the given CFG 𝑆 → 𝑏𝐴 /𝑎𝐵 𝐴 → 𝑏𝐴𝐴 /𝑎𝑆 /𝑎 𝐵 → 𝑎𝐵𝐵 /𝑏𝑆 /𝑏𝑏 Related searches: chomsky normal form chomsky normal form in toc chomsky normal form in toc tamil chomsky normal form context free grammar chomsky normal form and greibach normal form chomsky normal form examples chomsky normal form in flat chomsky normal form cnf chomsky normal form in automata chomsky normal form telugu Courses playlists: DISCRETE MATHEMATICS: https://www.youtube.com/playlist?list=PLS6nugESt9lLeVTXWMD_NXNVAKAC8RYDg THEORY OF COMPUTATION (TOC): https://www.youtube.com/playlist?list=PLS6nugESt9lJXt7UEXhQTyofeSrqQfPO3 DESIGN AND ANALYSIS OF ALGORITHMS (DAA)| ALGORITHM: https://www.youtube.com/playlist?list=PLS6nugESt9lJ2rluFZTYq8YnpRD1rm5Wf SYSTEM PROGRAMMING (SP): https://www.youtube.com/playlist?list=PLS6nugESt9lIGSB_qxapdJh46j_5Hwhlq DATA STRUCTURE: https://www.youtube.com/playlist?list=PLS6nugESt9lK1S3GnkUFVw5srnSYZPXDo #construct_moore_machine_find_residue_modulo5 #FSM #FLAT #shorttricks #cseacademy #regularexpression #finiteautomata #TOC #theoryofcomputation #conversion #conversion_of_fa_to_rg #ahmadsir #btech #btechcse #gatecse #engineering #pk #university