Chomsky Normal Form (CNF) Conversion Example

Easy Theory
Easy Theory
44.4 هزار بار بازدید - 4 سال پیش - Here we convert a context-free
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.
4 سال پیش در تاریخ 1399/01/12 منتشر شده است.
44,458 بـار بازدید شده
... بیشتر