\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{fancybox}
\newcounter{ques}
\newenvironment{question}{\stepcounter{ques}{\noindent\bf Question \arabic{ques}:}}{\vspace{5mm}}
%%%%%%%%%%%%%% Capsule %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\capsulenew}[1]{\vspace{0.5em}
\shadowbox{%
\begin{minipage}{.90\linewidth}%
#1%
\end{minipage}}
\vspace{0.5em} }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\begin{center} \Large\bf
COMP 3803 --- Assignment 3
\end{center}
\noindent {\bf Due:} Thursday November 25, 23:59.
\vspace{0.5em}
\noindent {\bf Assignment Policy:}
\begin{itemize}
\item Your assignment must be submitted as one single PDF file through
Brightspace.
\begin{center}
\hfill\shadowbox{
\begin{minipage}{.90\linewidth}
{\textsf{Use the following format to name your file:
\[ {\tt LastName\_StudentId\_a3.pdf}
\]
}}
\end{minipage}
}
\end{center}
\item {\bf Late assignments will not be accepted. I will not reply to
emails of the type ``my internet connection broke down at
23:57'' or ``my scanner stopped working at 23:58'', or
``my dog ate my laptop charger''.}
\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{0.5em}
\begin{question}
Write your name and student number.
\end{question}
\begin{question}
Consider the context-free grammar $G = (V,\Sigma,R,S)$, where the
set of variables is $V = \{S,A,B\}$, the set of terminals is
$\Sigma = \{a,b\}$, the start variable is $S$, and the rules are as
follows:
\[ \begin{array}{lcl}
S & \rightarrow & abB\\
A & \rightarrow & \epsilon \mid aaBb \\
B & \rightarrow & bbAa \\
\end{array}
\]
Prove that the language $L(G)$ that is generated by $G$ is equal to
\[ L(G) = \{ ab (bbaa)^n bba (ba)^n \mid n \geq 0 \} .
\]
(Remember: To prove that two sets $X$ and $Y$ are equal, you have to
prove that $X \subseteq Y$ and $Y \subseteq X$.)
\end{question}
\begin{question}
Give context-free grammars that generate the following languages. For
each case, justify your answer.
\noindent
{\bf (\arabic{ques}.1)}
$\{ a^{n+3} b^n \mid n \geq 0 \}$.
The set of terminals is equal to $\{a,b\}$.
\noindent
{\bf (\arabic{ques}.2)}
$\{ a^n b^m \mid n \geq 0, m \geq 0, 2n \leq m \leq 3n \}$.
The set of terminals is equal to $\{a,b\}$.
\noindent
{\bf (\arabic{ques}.3)}
$\{ a^m b^n c^n \mid m \geq 0, n \geq 0 \}$.
The set of terminals is equal to $\{a,b,c\}$.
\end{question}
\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{ques}.1)}
$\{ 0^{2n} 1^n \mid n \geq 0 \}$.
\noindent
{\bf (\arabic{ques}.2)}
$\{ w w^R \mid 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{ques}.1)}
$\{ a^{n!} \mid n \geq 0 \}$.
\noindent
{\bf (\arabic{ques}.2)}
$\{ a^{n^2} b^n \mid n \geq 0 \}$.
\end{question}
\begin{question}
We have seen that the regular languages are closed under the union,
intersection, complement, concatenation, and star operations.
In this question, we consider these operations for context-free
languages.
\noindent
{\bf (\arabic{ques}.1)}
Let $L$ and $L'$ be context-free languages over the same alphabet
$\Sigma$. Prove that the union $L \cup L'$ is also context-free.
\noindent
{\bf (\arabic{ques}.2)}
Let $L$ and $L'$ be context-free languages over the same alphabet
$\Sigma$. Prove that the concatenation $L L'$ is also context-free.
\noindent
{\bf (\arabic{ques}.3)}
Let $L$ be a context-free language over the alphabet $\Sigma$.
Prove that the star $L^*$ of $L$ is also context-free.
\noindent
{\bf (\arabic{ques}.4)}
In Question~1, you have shown that
\[ L = \{ a^m b^n c^n \mid m \geq 0, n \geq 0 \}
\]
is a context-free language. By a symmetric argument, the language
\[ L' = \{ a^m b^m c^n \mid m \geq 0, n \geq 0 \}
\]
is context-free.
Prove 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{ques}.5)}
Prove that the complement of a context-free language is not necessarily
context-free.
\end{question}
\end{document}