COT4210 Discrete Structures – Exam 2 Spring 2020 Exam 2 Solutions MATH 0201

COT4210 Discrete Structures – Exam 2 Spring 2020 1. (10) Let G = (V, ∑, R, S) be a grammar with V = {Q, R, T}; ∑ = {q, r, t}; and the set of rules: S  R Q  q | RqT R  r | rT | QQr T  t | S| tT Convert this grammar to a PDA using the method we described. 10 points for the conversion, use your judgment on partial credit. Do not deduct for simple notation errors. ε, S  R ε, Q  q ε, ε  S$ ε, Q  RqT ε, R  r ε, R  rT ε, R  QQr ε, T  t ε, T  S ε, T  tT q, q  ε ε, $  ε r, r  ε t, t  ε qACCEPT qLOOP q0 qACCEPT This study source was downloaded by from CourseH on :10:47 GMT -06:00 2. (15) Let G = (V, ∑, R, S) be a grammar with V = {Q, R, T}; ∑ = {q, r, t}; and the set of rules: S  R Q  q | RqT R  r | rT | QQr T  t | S | tT Convert G to Chomsky normal