20 views
is grammar CFG =    S->AS/epsilon

A->aA/a

in Chomsky Nomal form ?
0
i think its not in chomsky normal form.

second prodn should be A->AA /a

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$.

+1 vote
1
2
+1 vote