Let G = (V,E, R, S) be a context free grammar, where V = {(, ),...

 

Transcribed Image Text:

Let G = (V,E, R, S) be a context free grammar, where V = {(, ), a, ., S, A}, Σ = {(, ), ., a } and R = {S →(), Sa, S→(A), AS, A→ S.A} (20 pts) (a) Apply Heuristic rules (1) and/or (2) to G. Let G'be the resulting grammar. (20 pts) (b) Construct a deterministic pushdown automata M accepting L(G)$. (30 pts) (c) Study the computation of M on the string ((()).a). Let G = (V,E, R, S) be a context free grammar, where V = {(, ), a, ., S, A}, Σ = {(, ), ., a } and R = {S →(), Sa, S→(A), AS, A→ S.A} (20 pts) (a) Apply Heuristic rules (1) and/or (2) to G. Let G'be the resulting grammar. (20 pts) (b) Construct a deterministic pushdown automata M accepting L(G)$. (30 pts) (c) Study the computation of M on the string ((()).a).