heXcore

Appearance

CFG to CNF ​

CFG: The language generated by CFG is called Context Free Grammar ​

Simplification: ​

CNF: Chomskey Normal Form :- ​

A→BC [variables]
A→ a [Terminal]

A,B,C Represent Variables. a represents terminal

  • If there exist terminal at right side, then there must be only one terminal
  • If there exist variables at right side, Then there must be exactly TWO variables
  • No ε rules (S→ε) is allowed except START variable → ε
  • START variables cannot exist in the right of any product rules.

CNF Conversion: ​

EXAMPLE: 1 ​

S→ ASA|aB
A→ B  | S
B→ b  | ε

STEP 1: Add new start variable ​

L → S 
S→ ASA|aB
A→ B  | S
B→ b  | ε

STEP 2: Remove ε rules except Start Variable pointing to ε ​

B→ ε Removal: ​

  1. Remove ε
  2. Find out the ε containing variables in RIGHT side of other Rules
  3. ADD those variables with the ε with those Rules
L → S
S→ ASA|aB | a    [aB → aε == a]
A→ B  | S | ε    [B→ε == ε]
B→ b             [Remove ε from the Variable]

A→ ε Removal: ​

L → S
S→ ASA | aB | a | AS | SA | S [ASA → εSε  == S]
                              [ASA → εSA ==  SA]    
                              [ASA → ASε == AS]

A→ B  | S  [Remove ε from the Variable]
B→ b

STEP 3: unit rules (V → P)[right side single variable] Removal ​

Self Removal: S→ S ​

L → S
S→ ASA | aB | a | AS | SA [Removed S]
A→ B | S
B→ b

A → B Removal: ​

L → S
S→ ASA | aB | a | AS | SA [Removed S]
A→ b | S [Removed B]
         [A→ B → b == A → b]
B→ b

A→ S Removal: ​

L → S
S→ ASA | aB | a | AS | SA 
A→ b |ASA | aB | a | AS | SA  [Removed S]
                              [A→ S → ASA | aB | a | AS | SA]
B→ b

L → S Removal: ​

L → ASA | aB | a | AS | SA     [L → S → ASA | aB | a | AS | SA]
S→ ASA | aB | a | AS | SA 
A→ b |ASA | aB | a | AS | SA  
B→ b

STEP 4: Proper Form Conversion ​

L → AP | QB | a | AS | SA     [L → S → ASA | aB | a | AS | SA]
P    → SA
Q    → a
S    → AP | QB | a | AS | SA 
A    → b |AP | QB | a | AS | SA  
B     → b

We made two new Rules here:

  • in CNF there can be Maximum TWO variables but as We can see we have "ASA" 3 Variables. To reduced it to TWO variables We made the Below Rule

P → SA

  • in CNF nonTerminal(Variables) and Terminal can't be together, Also Maximum two variables can be declared simultaneously. To fix this issue, we made the Below Rule.

Q → a

The END!
This the Chomollokko Normal Form

Example 2: ​

A → BAB | B | ε 
B → 00 | ε

STEP 1: Add new start variable ​

S → A
A → BAB | B | ε 
B → 00 | ε

STEP 2: Remove ε rules except Start Variable pointing to ε ​

A → ε Removal: ​

S → A | ε
A → BAB | B | BB 
B → 00 | ε

B→ ε Removal: ​

S → A | ε
A → BAB | B | BB | BA | AB | A  [(B → ε == ε , BB → εε) == ε] 
                                [There supposed to be an ε . But in previous step we removed ε from B. So we don't need to add it again]
B → 00

STEP 3: unit rules (V → P)[right side single variable] Removal ​

Self Removal: A → A ​

S → A | ε
A → BAB | B | BB | BA | AB 
B → 00

A → B Removal: ​

S → A | ε
A → BAB | 00 | BB | BA | AB
B → 00

S → A Removal: ​

S → BAB | 00 | BB | BA | AB | ε 
A → BAB | 00 | BB | BA | AB
B → 00

STEP 4: Proper Form Conversion ​

S → BP | QQ | BB | BA | AB | ε
P → AB
Q → 0
A → BP | QQ | BB | BA | AB
B → QQ

The END!

Example 3: ​

S→ aXbX
X → aY | bY | ε
Y → X | c

CNF Conversion: ​

STEP 1: Add new start variable ​

L → S
S→ aXbX
X → aY | bY | ε
Y → X | c

STEP 2: Remove ε rules except Start Variable pointing to ε ​

X → ε Removal: ​
L → S
S → aXbX | aXb | abX | ab
X → aY | bY
Y → X | c | ε
Y → ε Removal: ​
L → S
S    → aXbX | aXb | abX | ab
X    → aY | bY | a | b
Y    → X | c

STEP 3: unit rules ​

Self Removal: ​

Nothing to remove

Single Variables Removal: ​
Y → X Removal ​
L    → S
S    → aXbX | aXb | abX | ab
X    → aY | bY | a | b
Y    → aY | bY | a | b | c
L → S Removal ​
L    → aXbX | aXb | abX | ab
S    → aXbX | aXb | abX | ab
X    → aY | bY | a | b
Y    → aY | bY | a | b | c

STEP 4: Proper Conversion ​

L    → PQ | PB | AQ | AB

A    → a
B    → b

P    → AX [aX]
Q    → BX [bX]

S    → PQ | PB | AQ | AB
X    → AY | BY | a | b
Y    → AY | BY | a |b | c

The END

Example 5: ​

S → aX | bY | b | ZZc
X → Yaa| abZ| ε 
Y → bXXb | ab | cZ
Z → a | b | XZ | ε

CNF Conversion: ​

STEP 1: ​

U → S
S → aX | bY | b | ZZc
X → Yaa| abZ| ε 
Y → bXXb | ab | cZ
Z → a | b | XZ | ε

STEP 2: ε Removal ​

X → ε Removal ​
U → S
S → aX | bY | b | ZZc | a
X → Yaa| abZ
Y → bXXb | ab | cZ | bXb | bb
Z → a | b | XZ | ε | Z
Z → ε Removal: ​
U → S
S → aX | bY | b | ZZc | a | Zc | c
X → Yaa| abZ | ab
Y → bXXb | ab | cZ | bXb | bb | c
Z → a | b | XZ | Z | X

STEP 3: Unit Removal ​

Self Removal: ​
Z → Z Removal: ​
U → S
S → aX | bY | b | ZZc | a | Zc | c
X → Yaa| abZ | ab
Y → bXXb | ab | cZ | bXb | bb | c
Z → a | b | XZ | X
Single Variable Removal: ​
Z → X Removal: ​
U → S
S → aX | bY | b | ZZc | a | Zc | c
X → Yaa| abZ | ab
Y → bXXb | ab | cZ | bXb | bb | c
Z → a | b | XZ | Yaa| abZ | ab
U → S Removal: ​
U → aX | bY | b | ZZc | a | Zc | c

S → aX | bY | b | ZZc | a | Zc | c
X → Yaa| abZ | ab
Y → bXXb | ab | cZ | bXb | bb | c
Z → a | b | XZ | Yaa| abZ | ab

STEP 4: Proper Conversion ​

U → AX | BY | b | DC | a | ZC | c
A → a
B → b
C → c
D → ZZ
S → AX | BY | b | DC | a | ZC | c
X → YE| FZ | AB
E → AA
F → AB
Y → GH | AB | CZ | GB | BB | c
G → BX
H → XB
Z → a | b | XZ | YE| FZ | AB