Chomsky Normal Form (CFG to CNF conversion), a Correct Proof - Easy Theory

Here we give a complete and correct proof of Chomsky Normal Form, which is a restricted form of context-free grammars, and the proof is that every CFG can be converted into CNF. Many proofs out there give a "hand-wavy" argument, but we give a technically sound argument at each step of the way. There are 5 stages - watch the video to find out what the 5 are!

Timestamps:
0:00 - Intro
3:00 - Definition of Chomsky Normal Form
7:30 - Proof of Step 1's correctness
12:15 - Proof of Step 2's correctness
20:20 - Proof of Step 3's correctness
27:13 - Proof of Step 4's correctness
30:42 - Proof of Step 5's correctness

Easy Theory Website:
Donation (appears on streams):
Paypal:
Patreon:
Discord:

#easytheory #gate #theory

Youtube Live Streaming (Sundays) - subscribe for when these occur.

Social Media:
Facebook Page:
Facebook group:
Twitter:

Merch:
Language Hierarchy Apparel:
Pumping Lemma Apparel:

If you like this content, please consider subscribing to my channel:

Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy

▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com

▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.

chomsky normal form,cfg to cnf,cfg to cnf conversion,conversion of cfg to cnf,conversion of cfg to chomsky normal form,context-free grammar to chomsky normal form,context-free grammar to cnf,chomsky normal form conversion,easy theory cnf,chomsky normal form example,cnf examples with solutions,cnf examples,context free grammar to chomsky normal form,convert context free grammar to chomsky normal form,easy theory,cnf conversion,