\documentclass[12pt]{article}
\usepackage{fullpage-old} \usepackage{fancyhdr}
\usepackage{amsmath}    \usepackage{amsfonts}   \usepackage{amssymb}
\usepackage{graphics}   \usepackage{epsfig}     \usepackage{wrapfig}
\usepackage{enumitem}

\lhead{} \cfoot[]{Page \thepage{}}%{ of 1}
\pagestyle{fancy} \renewcommand{\headrulewidth}{0pt}
\fancypagestyle{plain}{ \renewcommand{\headrulewidth}{0pt} }
\parskip 1ex
\parindent 0mm

\newcommand*{\ii}[1]{\textit{#1\/}}
\def\mi{\mathit}
\def\ttt{\texttt}
\def\ss{\hspace{1pt}}

% Logical operators
\def\andl{\wedge}
\def\orl{\vee}
\def\xorl{\oplus}
\def\notl{\neg}


\begin{document}

%{\flushright Name: \rule{15em}{0.25pt} \par} 
\vspace{-2ex}
{\center \Large FLAC Assignment 6\par}
\vspace{2ex}

%\begin{wrapfigure}{r}{3.3in}
%\vspace{-3ex}
%\includegraphics[scale=1.2]{hw2-fig.pdf}
%\end{wrapfigure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Exercise 1.} 
Give context-free grammars that generate the following languages.  In all parts
the alphabet is $\Sigma$ is $\{\ttt{0}, \ttt{1}\}$.
\begin{enumerate}[label=\bf\alph*.]
\item $\{w \;|\; \textrm{$w$ contains at least three \ttt{1}s}\}$
\item $\{w \;|\; \textrm{$w$ starts and ends with the same symbol}\}$
\item $\{w \;|\; \textrm{the length of $w$ is odd}\}$
\item $\{w \;|\; \textrm{the length of $w$ is odd and its middle symbol is a \ttt{0}}\}$
\item $\{w \;|\; \textrm{$w=w^R$, i.e., $w$ is a palindrome (of either odd or even length)}\}$
\item The empty set
\end{enumerate}
(Note: You may check your answers to parts (a) and (d) in the book; see
Exercise 2.4 on page 128 and 132.  But don't peek without first trying it yourself!)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Exercise 2.}  Give the state diagrams of pushdata automata for the following languages.

\begin{enumerate}[label=\bf\alph*.]
\item[\bf d.] The language of Exercise 1(d).
\item[\bf e.] The language of Exercise 1(e).
\item[\bf f.] $\{w{\ss}\ttt{\#}{\ss}v \;|\; \textrm{$w$ has more occurrences of \ttt{1}
than does $v$}\}$.  You may assume that the input string has no more than one
occurrence of ``\ttt{\#}''; strings with more than one ``\ttt{\#}'' are
don't-care inputs that can be ignored to simplify the design of your PDA.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Exercise 3.}  Show the intersection of a context-free language
$C$ with a regular language~$R$ is always context-free.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Exercise 4.}  Show that the language 
$\{\ttt{0}^n \ttt{1}^m \ttt{0}^n \ttt{1}^m \;|\; n \ge 0\}$
is not context-free.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Exercise 5.}  Show that the language 
$\{w{\ss}w \;|\; w \in (\ttt{0}\!+\!\ttt{1})^*\}$
is not context-free.  
\\ Hint: Intersect with $\ttt{0}^* \ttt{1}^* \ttt{0}^* \ttt{1}^*$ and use the
results from Exercises 3 and 4.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Exercise 6 (bonus).}  Is the following language context-free?  Prove your answer.
$$\{w{\ss}w' \;\;|\;\; w \in (\ttt{a}\!+\!\ttt{b})^*,\;
w' \in (\ttt{a}\!+\!\ttt{b})^*,\; w \neq w',\,\textrm{ and }\; |w|=|w'|\}$$

\end{document}
