Chomsky Normal Form (CNF) Conversion Example скачать в хорошем качестве

Chomsky Normal Form (CNF) 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! 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.