Question

Give a Context Free Grammar (CFG) that accepts the following regular expression (abb + b)*(ab)* + ɛ and convert into an equivalent CFG in Chomsky Normal Form (CNF).

Answer 1

Answer:

Explanation:

Step 1 − If the start symbol S occurs on some right side, create a new start symbol S' and a new production S'→ S.

Step 2 − Remove Null productions. ( ...

Step 3 − Remove unit productions. ( ...

Step 4 − Replace each production A → B1…