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: www.easytheory.org
Discord: / discord
If you like this content, please consider subscribing to my channel: / @easytheory
▶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 - what is it?
Пікірлер: 19