# Chapter 2: Chapter 2

Problem 37

Prove the following stronger form of the pumping lemma, wherein botb pieces \(v\) and \(y\) must be nonempty when the string \(s\) is broken up. If \(A\) is a context-free language, then there is a number \(k\) where, if \(s\) is any string in \(A\) of length at least \(k\), then \(s\) may be divided into five pieces, \(s=u v x y z\), satisfying the conditions: a. for each \(i \geq 0, u v^{i} x y^{i} z \in A\), b. \(v \neq \varepsilon\) and \(y \neq \varepsilon\), and c. \(|v x y| \leq k\).

Problem 4

Give context-free grammars that generate the following languages. In all parts, the lphabet \(\Sigma\) is \(\\{0,1\\}\). A a. \(\\{w \mid w\) contains at least three 1 s \(\\}\) b. \(\\{w \mid w\) starts and ends with the same symbol \(\\}\) c. \(\\{w \mid\) the length of \(w\) is odd \(\\}\) Af. \(\\{w \mid\) the length of \(w\) is odd and its middle symbol is a 0\(\\}\) e. \(\left\\{w \mid w=w^{\mathcal{R}}\right.\), that is, \(w\) is a palindrome \(\\}\) f. The empty set

Problem 40

Say that a language is prefix-closed if all prefixes of every string in the language are also in the language. Let \(C\) be an infinite, prefix-closed, context-free language. Show that \(C\) contains an infinite regular subset.

Problem 43

For strings \(w\) and \(t\), write \(w \doteq t\) if the symbols of \(w\) are a permutation of the symbols of \(t .\) In other words, \(w \doteq t\) if \(t\) and \(w\) have the same symbols in the same quantities, but possibly in a different order. For any string \(w\), define \(S C R A M B L E(w)=\\{t \mid t \doteq w\\}\). For any language \(A\), let \(S C R A M B L E(A)=\\{t \mid t \in S C R A M B L E(w)\) for some \(w \in A\\} .\) a. Show that if \(\Sigma=\\{0,1\\}\), then the SCRAMBLE of a regular language is context free. b. What happens in part (a) if \(\Sigma\) contains three or more symbols? Prove your answer.

Problem 44

If \(A\) and \(B\) are languages, define \(A \diamond B=\\{x y \mid x \in A\) and $y \in B\( and \)|x|=|y|\\}\(. Show that if \)A\( and \)B$ are regular languages, then \(A \diamond B\) is a \(C F L\).

Problem 45

Let \(A=\left\\{w t w^{\mathcal{R}} \mid w, t \in\\{0,1\\}^{*}\right.\) and \(\left.|w|=|t|\right\\}\). Prove that \(A\) is not a CFL.

Problem 46

Consider the following CFG \(G\) : $$ \begin{aligned} &S \rightarrow S S \mid T \\ &T \rightarrow \mathrm{a} T \mathrm{~b} \mid \mathrm{ab} \end{aligned} $$ Describe \(L(G)\) and show that \(G\) is ambiguous. Give an unambiguous grammar \(H\) where \(L(H)=L(G)\) and sketch a proof that \(H\) is unambiguous.

Problem 47

Let \(\Sigma=\\{0,1\\}\) and let \(B\) be the collection of strings that contain at least one 1 in their second half. In other words, $B=\left\\{u v \mid u \in \Sigma^{*}, v \in \Sigma^{*} 1 \Sigma^{*}\right.\( and \)\left.|u| \geq|v|\right\\}$. a. Give a PDA that recognizes \(B\). b. Give a CFG that generates \(B\).

Problem 48

Let \(\Sigma=\\{0,1\\} .\) Let \(C_{1}\) be the language of all strings that contain a 1 in their middle third. Let \(C_{2}\) be the language of all strings that contain two \(1 \mathrm{~s}\) in their middle third. So $C_{1}=\left\\{x y z \mid x, z \in \Sigma^{*}\right.\( and \)y \in \Sigma^{*} 1 \Sigma^{*}$, where \(\left.|x|=|z| \geq|y|\right\\}\) and $C_{2}=\left\\{x y z \mid x, z \in \Sigma^{*}\right.\( and \)y \in \Sigma^{*} 1 \Sigma^{*} 1 \Sigma^{*}$, where \(\left.|x|=|z| \geq|y|\right\\}\). a. Show that \(C_{1}\) is a \(\mathrm{CFL}\). b. Show that \(C_{2}\) is not a CFL.

Problem 52

Show that every DCFG generates a prefix-free language.