convert context-free-grammar to Chomsky normal form

346 Views Asked by At

I'm trying to convert this context-free grammar to CNF:

S -> AB | a | epsilon

A -> a | C | Ca | epsilon

B -> C

C -> Ca | Cb | D

D -> Ca | a

is it this answer true :

S -> AB | a | epsilon | CX | CY

A -> a | CY | CX

B -> a | CY | CX

C -> a | CY | CX

X -> a

Y -> b

1

There are 1 best solutions below

0
Bharath K On

Start symbol generating ε. For example, A → ε. A non-terminal generating two non-terminals. For example, S → AB. A non-terminal generating a terminal. For example, S → a. Your answer satisfied all three conditions of Chomsky normal form. Hence your answer is correct