Question

Convert the following grammars into Chomsky Normal Form

(a) S→ASB∣ϵ,A→aAS∣a,B→SbS∣A∣bb.
(b) S→0A0∣1B1∣BB,A→C,B→S∣A,C→S∣ϵ.

Answer 1

To convert grammars into Chomsky Normal Form, new non-terminal symbols need to be created for each terminal symbol, and productions with more than two non-terminals must be eliminated. For grammar (a), the converted form is S → ADT | ϵ, A → aAS | a, D → A, T → SP | SB, B → SPT | A | bb, P → bS. For grammar (b), the converted form is S → YTZ | XYX | ZZ, A → C, B → YT | XY | ZZ | A, C → YT | XY | ZZ | ϵ, X → 1, Y → 0, Z → B.

Step-by-step explanation:

To convert the given grammars into Chomsky Normal Form, we need to follow two main rules:

1. Create new non-terminal symbols for each terminal symbol.
2. Eliminate any productions with more than two non-terminals.

For grammar (a), we can apply the rules as follows:

• S → ASB | ϵ
• A → aAS | a
• B → SbS | A | bb

Step 1: Create new non-terminal symbols for each terminal symbol:

• S → ADT | ϵ
• A → aAS | a
• D → A
• T → SB
• B → SPT | A | bb
• P → bS

Step 2: Eliminate productions with more than two non-terminals:

• S → ADT | ϵ
• A → aAS | a
• D → A
• T → SP | SB
• B → SPT | A | bb
• P → bS

For grammar (b), we can apply the rules as follows:

• S → 0A0 | 1B1 | BB
• A → C
• B → S | A
• C → S | ϵ

Step 1: Create new non-terminal symbols for each terminal symbol:

• S → YTZ | XYX | ZZ
• A → C
• B → S | A
• C → S | ϵ
• X → 1
• Y → 0
• Z → B

Step 2: Eliminate productions with more than two non-terminals:

• S → YTZ | XYX | ZZ
• A → C
• B → YT | XY | ZZ | A
• C → YT | XY | ZZ | ϵ
• X → 1
• Y → 0
• Z → B