Need Help to convert a grammar into Chomsky Form

173 Views Asked by At

I have to convert the following grammar into Chomsky Form $$( \Sigma=\{a,b,c,+\}, \Sigma_Q=\{S,V\},I=S)$$ $$S -> S+S|V$$ $$V -> a|b|c$$

My idea is the following: $$S_0 \rightarrow S$$ $$S \rightarrow ST|V$$ $$T \rightarrow +S$$ $$V \rightarrow A|B|C$$ $$A \rightarrow a$$ $$B \rightarrow b$$ $$C \rightarrow c$$

Could you tell me if this is right?

1

There are 1 best solutions below

9
On BEST ANSWER

In a grammar in Chomsky normal form there can only be two types of productions: $A\to BC$ and $A\to a$ where $A,B,C$ are nonterminals (variables, $\Sigma_Q$ in your notation) and $a$ is terminal ($\Sigma$ in your notation).

In particular, "chain productions" which are of the form $A\to B$ are not allowed. You have several of them. In particular, the original productions $V\to a\mid b\mid c$ were OK, while the new $V\to A\mid B\mid C$ isn't.

You have also introduced a special start symbol $S_0$. In the definition of Chomsky as I know it that s not necessary. Also note your production $T\to +S$ is of "mixed type" (it has both a terminal and a nonterminal) and is illegal.