\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}