Theory of Computation207910 marksNumerical: Grammar left recursion CNF conversionChomsky Normal Form
Given the following expression grammar for simple arithmetic expression with operator + and *. Remove the left recursion from this grammar then simplify and convert to CNF.E→E+T∣TE \rightarrow E+T \mid TE→E+T∣TT→T+F∣FT \rightarrow T+F \mid FT→T+F∣FF→(E)∣aF \rightarrow (E) \mid aF→(E)∣a
Given the following expression grammar for simple arithmetic expression with operator + and *. Remove the left recursion from this grammar then simplify and convert to CNF.E→E+T∣TE \rightarrow E+T \mid TE→E+T∣TT→T+F∣FT \rightarrow T+F \mid FT→T+F∣FF→(E)∣aF \rightarrow (E) \mid aF→(E)∣a[10]
The grammar as literally written in the question: $$E \to E+T \mid T$$ $$T \to T+F \mid F$$ $$F \to (E) \mid a$$ Note on interpretation: The problem statement says "operators + and ", but the middle rule is written with + again. The standard expression grammar uses in the T rule. I will follow th...