Problem Set 4 Solution

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.)