Chapter 2: Chapter 2

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

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

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.

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.

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

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.

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.

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

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.

Show that every DCFG generates a prefix-free language.