\documentclass[12pt]{article}
\usepackage{amssymb}
\usepackage{fullpage}
\newcounter{que}
\newenvironment{question}{\stepcounter{que}{\noindent\bf Question \arabic{que}: }}{\vspace{5mm}}
\begin{document}
\begin{center} \Large\bf
COMP 3803 --- Assignment 3
\end{center}
\noindent {\bf Due:} Thursday March 21, before 11:55pm.
\vspace{0.5em}
\noindent {\bf Assignment Policy:}
\begin{itemize}
\item Your assignment must be submitted as one single PDF file through
cuLearn.
\item Late assignments will not be accepted.
\item You are encouraged to collaborate on assignments, but at the level
of discussion only. When writing your solutions, you must do so
in your own words.
\item Past experience has shown conclusively that those who do not put
adequate effort into the assignments do not learn the material and
have a probability near 1 of doing poorly on the exams.
\item When writing your solutions, you must follow the guidelines below.
\begin{itemize}
\item You must justify your answers.
\item The answers should be concise, clear and neat.
\item When presenting proofs, every step should be justified.
\end{itemize}
\end{itemize}
\vspace{1em}
\begin{question}
Give context-free grammars that generate the following languages. For
each case, justify your answer.
\noindent
{\bf (\arabic{que}.1)}
$\{ 0^{2n} 1^n | n \geq 0 \}$.
The set $\Sigma$ of terminals is equal to $\{0,1\}$.
\noindent
{\bf (\arabic{que}.2)}
$\{ w | w \mbox{ starts and ends with different symbols} \}$.
The set $\Sigma$ of terminals is equal to $\{0,1\}$.
\noindent
{\bf (\arabic{que}.3)}
$\{ w | \mbox{ $w$ is a palindrome} \}$.
The set $\Sigma$ of terminals is equal to $\{0,1\}$. \\
A \emph{palindrome} is a string $w$ having the property
that $w = w^R$, i.e., reading $w$ from left to right
gives the same result as reading $w$ from right to left.
For example, the four binary strings $\epsilon$, $1$, $0110$, and
$10101$ are palindromes.
\noindent
{\bf (\arabic{que}.4)}
$\{ a^m b^n c^n | m \geq 0, n \geq 0 \}$.
The set $\Sigma$ of terminals is equal to $\{a,b,c\}$.
\end{question}
\begin{question}
Let $L$ and $L'$ be context-free languages over the same alphabet
$\Sigma$.
\noindent
{\bf (\arabic{que}.1)}
Prove that the union $L \cup L'$ of $L$ and $L'$ is also context-free.
\noindent
{\bf (\arabic{que}.2)} Prove that the concatenation $L L'$ of $L$
and $L'$ is also context-free.
\noindent
{\bf (\arabic{que}.3)} Prove that the star $L^*$ of $L$ is also
context-free.
\end{question}
\newpage
\begin{question}
Give (deterministic or nondeterministic) pushdown automata that
accept the following languages. For each pushdown automaton, start
by explaining the algorithm in plain English, then mention the states
that you are going to use, then explain the meaning of these states,
and finally give the list of instructions.
\noindent
{\bf (\arabic{que}.1)}
$\{ 0^{2n} 1^n | n \geq 0 \}$.
\noindent
{\bf (\arabic{que}.2)}
$\{ w w^R | w \in \{0,1\}^* \}$. \\
(If $w = w_1 \ldots w_n$, then $w^R = w_n \ldots w_1$.)
\end{question}
\begin{question}
Prove that the following languages are not context-free:
\noindent
{\bf (\arabic{que}.1)}
$\{ 0^n \, 1 \, 0^{2n} \, 1 \, 0^{3n} | n \geq 0 \}$.
\noindent
{\bf (\arabic{que}.2)}
\[ \begin{array}{lcl}
\{ \ w \in \{a,b,c\}^* & | &
\mbox{$w$ contains more $b$'s than $a$'s {\bf and}} \\
& & \mbox{$w$ contains more $c$'s than $a$'s} \ \} .
\end{array}
\]
\end{question}
\begin{question}
In Question~1, you have shown that
\[ L = \{ a^m b^n c^n | m \geq 0, n \geq 0 \}
\]
is a context-free language. By a symmetric argument, the language
\[ L' = \{ a^m b^m c^n | m \geq 0, n \geq 0 \}
\]
is context-free.
\noindent
{\bf (\arabic{que}.1)}
Argue that the intersection of two context-free languages is not
necessarily context-free. (You may use any result that was proven in
class.)
\noindent
{\bf (\arabic{que}.2)}
Argue that the complement of a context-free language is not necessarily
context-free.
\end{question}
\end{document}