Problem 1. (10 points) Convert the following CFG into a PDA using the conversion discussed in
class (Lemma 2.21 in the textbook):
πΈπΈ → πΈπΈ + ππ | ππ
ππ → ππ × πΉπΉ | πΉπΉ
πΉπΉ → (πΈπΈ) | ππ
Problem 2. (10 points) For each of the following languages, either give a CFG generating it, or a
high-level description of a PDA that recognizes it:
a) The complement of {ππππππππ | ππ ≥ 0}
b) {π₯π₯1#π₯π₯2# β― π₯π₯ππ |ππ ≥ 1, ππππππβ π₯π₯ππ ∈ {ππ, ππ}∗ ππππππ ππππππ π π π π π π π π ππ,ππ π₯π₯ππ = π₯π₯ππ
π
π
}
Problem 3. (10 points) Let πΆπΆ be a context-free language, and π
π
be a regular language. Show
that the language πΆπΆ ∩ π
π
is context free. Start with a PDA (ππ, Σ, Γ, πΏπΏ, πππ π π π π π π π π π , πΉπΉ) for πΆπΆ and a DFA
οΏ½ππ′
, Σ′
, πΏπΏ′
, ππ′
π π π π π π π π π π , πΉπΉ′
οΏ½ for π
π
, then describe a PDA for πΆπΆ ∩ π
π
. Your description may be informal
and high-level (i.e. you don’t need to define detailed transitions), but must be precise.
Problem 4. (10points) Use the result of Problem 3 to prove that the language
πΏπΏ = {π€π€ ∈ {ππ, ππ, ππ}∗: π€π€ has equal numbers of ππ′
π π , ππ′
π π , and ππ′
π π } is not context free.
You may assume that the language {ππππππππππππ: ππ ≥ 0} is not context free.
(Hint: design a regular expression π
π
such that πΏπΏ ∩ π
π
is not context free.)
