Question

7. Convert the following grammar into Chomsky Normal Form.

S→aB
A→bAA
S→bA
B→b
A→a
B→bS
A→aS
B→aBB

Answer 1

To convert the given grammar into Chomsky Normal Form (CNF), we need to introduce new non-terminal symbols, eliminate ε-productions, remove unit productions, and replace long productions. After applying these steps, the CNF is obtained.

Step-by-step explanation:

The given grammar is as follows:

S → aBA
A → bAAS
A → bAB
B → bA
A → aB
S → bS
S → aB
B → aSB
B → aBB

To convert the grammar into Chomsky Normal Form (CNF), we need to follow these steps:

1. Create new non-terminal symbols for each terminal symbol in the grammar. For example, introduce a new symbol X for the terminal a.
2. Create new non-terminal symbols to handle productions with more than two symbols. For example, if we have a production A → BC, introduce a new symbol Y and replace the production with A → BY, Y → BC.
3. Eliminate ε-productions by removing any productions that have ε as a right-hand side and adding new productions to account for the empty string.
4. Remove unit productions by replacing them with the corresponding productions from the original grammar.
5. Replace long productions by introducing new symbols to handle the extra non-terminal symbols.

After applying these steps to the given grammar, we obtain the CNF as follows:

S → XY
X → AZ
A → YZ
A → XY
B → XZ
S → YZ
S → AX
S → XY
B → AY
B → AB