Theory of Computation20785 marksChomsky Normal Form
Construct the following grammar into Chomsky Normal Form. S→abSb∣a∣aAbS \rightarrow abSb \mid a \mid aAbS→abSb∣a∣aAbA→bS∣aAAb∣εA \rightarrow bS \mid aAAb \mid \varepsilonA→bS∣aAAb∣ε
Construct the following grammar into Chomsky Normal Form. S→abSb∣a∣aAbS \rightarrow abSb \mid a \mid aAbS→abSb∣a∣aAbA→bS∣aAAb∣εA \rightarrow bS \mid aAAb \mid \varepsilonA→bS∣aAAb∣ε[5]
$$S \rightarrow abSb \mid a \mid aAbS$$ $$A \rightarrow bS \mid aAAb \mid \varepsilon$$ --- CNF requires every production to be of the form: - $A \rightarrow BC$ (two non-terminals), or - $A \rightarrow a$ (single terminal) --- Identify nullable variables: A → ε, so A is nullable. Remove