125k views
1 vote
18. Convert the grammar G: SaA | ABa A → AA la B→ AbB | bb to Chomsky normal form. G already satisfies the conditions on the start symbol S, A-rules, useless symbols, and chain rules.

User Bcmpinc
by
8.4k points

1 Answer

6 votes

S → X2A2 | ABa

A → AC

C → A

B → X1B1 | bb

B1 → bB

A2 → a

Step-by-step explanation:

To convert the grammar G to Chomsky normal form (CNF), we need to eliminate productions with more than two non-terminals on the right-hand side and handle productions with terminals.

1. Convert A-rules to CNF:

- The production A → AA can be replaced by introducing a new non-terminal. Let's say we introduce a new non-terminal C. So, A → AC can be added, and then C → A can be added to handle the remaining production C → A.

- Now the A-rules are in CNF: A → AC and C → A.

2. Convert B-rules to CNF:

- The production B → AbB can be split into two productions: B → X1B1 and B1 → bB, where X1 is a new non-terminal. This breaks down the production into two non-terminals, each with a single terminal or non-terminal.

- The production B → bb already satisfies CNF as it has two terminals.

3. Convert S-rules to CNF:

- The production S → aA can be rewritten as S → X2A2, where X2 is a new non-terminal, and A2 → a.

Now the grammar G in CNF is:

S → X2A2 | ABa

A → AC

C → A

B → X1B1 | bb

B1 → bB

A2 → a

The grammar G is now in Chomsky normal form, where all productions have either two non-terminals or a single terminal.

User Dortique
by
7.9k points

Related questions