TOC - CFG

Question

is grammar CFG =    S->AS/epsilon

                                    A->aA/a

in Chomsky Nomal form ?

Comments

i think its not in chomsky normal form.

second prodn should be A->AA /a

Answer 1

A grammar is in Chomsky normal form if the productions are of the form:

$$A \rightarrow BC  \;\text{or} \\
A \rightarrow a \; \text{or} \\
S \rightarrow \epsilon$$

where $A,B,C$ are non-terminal symbols and $S$ is the starting symbol and $a$ is a terminal.

In your grammar, due to the presence of $A \rightarrow aA$, it is not in CNF.

It can be converted into CNF by replacing $A \rightarrow aA$ as $A \rightarrow X, X \rightarrow a$.