Theory of Computation20815 marksChomsky Normal Form
Convert the following grammar to CNF. S→AAB,A→aA∣ε,B→ab∣aS \rightarrow AAB, \quad A \rightarrow aA \mid \varepsilon, \quad B \rightarrow ab \mid aS→AAB,A→aA∣ε,B→ab∣a
Convert the following grammar to CNF. S→AAB,A→aA∣ε,B→ab∣aS \rightarrow AAB, \quad A \rightarrow aA \mid \varepsilon, \quad B \rightarrow ab \mid aS→AAB,A→aA∣ε,B→ab∣a[5]
$$S \rightarrow AAB, \quad A \rightarrow aA \mid \varepsilon, \quad B \rightarrow ab \mid a$$ --- CNF requires: Every production is either of the form A → BC (two non-terminals) or A → a (single terminal). No null productions (except possibly S → ε if ε ∈ L(G)). --- Identify nullable variables: A...