Problem 1. Let L be the language consisting of all strings over {a, b} that have twice as many as as bs. For example, aababa ∈ L and ϵ ∈ L but a not∈ L.
(a) Construct a context free grammar for L.
(b) Prove that your grammar is correct.
Hint:
• Show that for w ∈ {a, b}∗ if S →n w then w ∈ L by induction on the number of steps n in the
derivation of w, where S is a start symbol.
• Show that if w ∈ L then S →∗
w, and the proof can be carried out by induction on |w|.
Problem 2. Consider the language L = {x not =y | x, y ∈ {0, 1}∗ and x not = y}.
(a) Design a pushdown automaton for the language L.
(b) Design a context free grammar for the language L.
Problem 3. A right regular grammar (RRG) is a context-free grammar G = (N, Σ, P, S) such that all the production rules of P are of one of the following forms:
• A → aB, where A, B ∈ N , a ∈ Σ
• A → ϵ, where A ∈ N
(a) Let M = (Q, Σ, δ, s, F ) be a DFA. Construct a RRG G = (N, Σ, P, S) such that L(G) = L(M ).
(b) Prove that the construction is correct, that is, L(G) = L(M ).
(i) Show w ∈ L(G) ⇒ w ∈ L(M ) using induction on the length of derivations.
Hint: For a certain grammar, it can be shown that if q1 wq2 then δ(q1, w) = q2 using induction on the length of of derivations.
(ii) Show w ∈ L(M ) ⇒ w ∈ L(G) using induction on the length of w.
Hint: For a certain grammar, it can be shown that if δ(q1, w) = q2 then q1 → wq2 using induction on the length of |w|.