Chomsky Normal Form CNF Conversion Example

>> YOUR LINK HERE: ___ http://youtube.com/watch?v=-SZkkMWHBvQ

Here we convert a context-free grammar into Chomsky Normal Form, and show that it works for any CFG. The process involves 5 stages: (1) ensure the start variable is not on the RHS of any rule, (2) eliminate epsilon-rules, (3) eliminate unit rules, (4) ensure the RHS is only variables or a single terminal, and (5) reduce long RHSes. The order of the rules is important! • Timestamps: • 0:00 - Intro • 1:30 - Step 1 (ensure start var not on RHS) • 3:25 - Step 2 ( eliminate epsilon rules) • 9:10 - Step 3 ( eliminate unit rules) • 13:48 - Step 4 (remove mix of terminals and vars) • 17:18 - Step 5 (ensure RHSes are of length at most 2) • If you like this content, please consider subscribing to my channel: / @easytheory • ▶ADDITIONAL QUESTIONS◀ • 1. Can you prove why it is the case that each stage never changes the language of the CFG? • 2. What if we have a regular grammar and convert it to CNF? (i.e., every rule is either A to epsilon, A to a single terminal, A to a variable B, or A to xB where x is a terminal, B a variable) • ▶SEND ME THEORY QUESTIONS◀ • [email protected] • ▶ABOUT ME◀ • I am a professor of Computer Science, and am passionate about CS theory. I have taught over 12 courses at Arizona State University, as well as Colgate University, including several sections of undergraduate theory.

#############################

New on site