chapter2.tex

\section{Chapter 2}

%		2.3		%
\begin{enumerate}
\item[2.3]Answer each part for the following context-free grammar $G$.
\begin{align*}
R &\rightarrow XRX | S \\
S &\rightarrow aTb | bTa \\
T &\rightarrow XTX | X | \epsilon \\
X &\rightarrow a | b
\end{align*}
\textbf{Solution:} \alreadyanswered

%		2.7		%
\item[2.7]Give informal English descriptions of PDAs for the languages in Exercise 2.6.
\\
\textbf{Solution:} \alreadyanswered

%		2.8		%
\item[2.8]Show that the string \verb|the girl touches the boy with the flower| has two different leftmost derivations in grammar $G_2$ on page 103. Describe in English the two different meanings of this sentence.
\\
\textbf{Solution:} \alreadyanswered

%		2.9		%
\item[2.9]Give a context-free grammar that generates the language
\begin{center}
$A = \{a^ib^jc^k\;\vert\;i=j\;\text{or}\;j=k\;\text{where}\;i,j,k\ge 0\}$
\end{center}
Is your grammar ambiguous? Why or why not?
\\
\textbf{Solution:} construct a CFG $G = (S, A, B, C, D\}, \{a, b, c\}, R, S)$ with the rules:
\begin{align*}
S \rightarrow BC\;\vert\;AD\\
B \rightarrow aBb\;\vert\;\epsilon \\
C \rightarrow cC\;\vert\;\epsilon \\
A \rightarrow aA\;\vert\;\epsilon \\
D \rightarrow bDc\;\vert\;\epsilon \\
\end{align*}
Yes it is ambiguous. Choose the word $abc$. The two derivations are:
\begin{enumerate}
\item $S \rightarrow BC \rightarrow aBbC \rightarrow abC \rightarrow abcC \rightarrow abc$,
\item $S \rightarrow AD \rightarrow aAD \rightarrow aD \rightarrow abDc \rightarrow abc$.
\end{enumerate}

%		2.18		%
\item[2.18]
\begin{enumerate}
\item[a.]Let $C$ be a context-free language and $R$ be a regular language. Prove that the language $C \cap R$ is context free.
\\
\textbf{Solution:} \alreadyanswered

\item[b.]Let $A = \{w$ $|$ $w \in \{a, b, c\}^*$ and $w$ contains equal numbers of $a$?s, $b$?s, and $c$'s\}. Use part (a) to show that $A$ is not a CFL.
\\
\textbf{Solution:} \alreadyanswered
\end{enumerate}

%		2.24		%
\item[2.24]Let $E = \{a^ib^j \vert i \ne j\;\text{and}\;2i \ne j\}$. Show that $E$ is a context-free language.
\\
\textbf{Solution:} This is a partition of 3 languages: $L_1, L_2, L_3$ (i.e., it is their union). They are defined as follows: 
\begin{itemize}
\item $L_1 = \{a^ib^j \vert i > j\}$,
\item $L_2 = \{a^ib^j \vert i < j\;\text{and}\;2i > j\}$,
\item $L_3 = \{a^ib^j \vert 2i < j\}$.
\end{itemize}
It suffices to show that $L_1, L_2, L_3$ are all context-free languages. They are due to the following grammars:
\par $L_1$:
\begin{itemize}
\item $S \to aSb \vert aA$,
\item $A \to aA \vert \epsilon$
\end{itemize}
\par $L_2$:
\begin{itemize}
\item $S \to aAb$,
\item $A \to aAb \vert aAbb \vert abb$.
\end{itemize}
\par $L_3$:
\begin{itemize}
\item $S \to aSbb \vert Ab$,
\item $A \to Ab \vert \epsilon$
\end{itemize}

%		2.30		%
\item[2.30]Use the pumping lemma to show that the following languages are not context free.
\begin{enumerate}
\item[b.]\textbf{Solution:} \alreadyanswered
\item[c.]\textbf{Solution:} \alreadyanswered
\end{enumerate}

%		2.38		%
\item[2.38]Refer to Problem 1.41 for the definition of the perfect shuffle operation. Show that the class of context-free languages is not closed under perfect shuffle.
\\
\textbf{Solution:} \alreadyanswered

%		2.52		%
\item[2.52]Show that every DCFG generates a prefix-free language.
\\
\textbf{Solution:} \alreadyanswered

\end{enumerate}