0
$\begingroup$

I am reading the book "Automata, Formal Languages, and Automata" written by Dr. Emre Sermutlu and in page 153, it is stated that the following grammars are not in Chomsky Normal Definition (CNF):

$G_1$ :
$S\rightarrow TT\mid a$
$T\rightarrow ST \mid b$

$G_2$ :
$S \rightarrow TT \mid a$
$T \rightarrow a \mid b \mid \varepsilon$

The definition of Chomsky Normal Form is defined here: (https://en.wikipedia.org/wiki/Chomsky_normal_form). Why G1 and G2 are not CNF?

Improve this question
$\endgroup$
1
  • $\begingroup$ This is a matter of definitions, so be careful when using other sources. In the definition I adhere to, the grammar $G_1$ is a fine example of ChNF, where we allow productions of the form $A\to BC$ and $A\to a$. See for example the books of Linz or Martin. Or, as a matter of fact in the original definition of Chomsky himself. See my answer here for a link cs.stackexchange.com/a/92437/4287 $\endgroup$
    – Hendrik Jan
    Commented Nov 23, 2022 at 10:50

1 Answer 1

Reset to default
2
$\begingroup$

For the first one, the transition $T\rightarrow ST$ is not allowed, because in a transition $A\rightarrow BC$, neither $B$ nor $C$ must be the start symbol.

For the second one, the transition $T\rightarrow \varepsilon$ is not allowed, because only the start symbol ($S$) can be replaced with $\varepsilon$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.