*middle of document…*

(i). Provide a transition table showing each state, the inputs, and the resulting new states for each input

(ii). Represent your transition table into a digraph (transition diagram)

(2) Here is a context-free grammar that can be used to generate algebraic expressions via the arithmetic operators (addition, subtraction, multiplication, and division), in the variables p, q, and r. The letter E stands for expression:

Rule 1: E —› p

Rule 2: E —› q

Rule 3: E —› r

Rule 4: E —› E + E

Rule 5: E —› E – E

Rule 6: E —› E X E

Rule 7: E —› E/E

Rule 8: E —›(E)

(i). Use the above grammar to derive the string given by the mathematical expression E = (p + q) X p – r X p/(q + q)

E * E

E * E * E

E * E * E/E

(E) * E * E/E

(E + E) * E * E/E

(P+E) * E * E /E

(P + Q) * E * E/E

(P +Q) * (E0 * E/E

(P + Q) * (E - E) * E/E

(P + Q) * (P - R) * E/E

(P + Q) * (P - R) * P/E

(P + Q) * (P - R) * P/(E + E)

(P + Q) * (P - R) * P/(Q + E)

(P + Q) * (P - R) * P/(Q + Q)

(ii.) Provide a Parse tree for the derivation.