Chomsky Normal Form Conversion Example ✨

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!

Easy Theory Website: https://www.easytheory.org
GoFundMe: https://www.gofundme.com/f/easy-theory-video-studio
Patreon: https://www.patreon.com/EasyTheoryYT
Fourthwall: https://easy-theory-llc-shop.fourthwall.com
Problem Solving channel: ​⁠ @easytheoryprobsolve

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: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1