## Description

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