CMPT 364 — Assignment #5 XXXXXXXXXXT2 Due: Wednesday April 8, 2020 at 10:00pm 1. Create a PDA accepting the following languages: (a) {w | no prefix of w has more 1’s than 0’s}, (b) {vwvR | w, v ∈ {0,...

See the attachment


CMPT 364 — Assignment #5 2019-2020 T2 Due: Wednesday April 8, 2020 at 10:00pm 1. Create a PDA accepting the following languages: (a) {w | no prefix of w has more 1’s than 0’s}, (b) {vwvR | w, v ∈ {0, 1}∗}. 2. Consider the context-free grammar G = ({S, T}, {a, b, c}, P, S), where • S → aScc | T , • T → bTcc | �. (a) Describe the language this generates? (b) Convert it to a PDA accepting the same language. 3. Prove that {aibncj | 0 ≤ i ≤ n, 0 ≤ j ≤ n} is not context-free. 4. Prove that {a1ba2b · · · aib | i > 0} is not context-free. 1