%
% Assignment 3a for CS3530 Computational Theory:
% Regular Languages
% Fall 2024
%
% Problems taken from Sipser
%

\documentclass{article}

\usepackage[margin=1in]{geometry}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{ae,aecompl}
\usepackage{emp,ifpdf}
\usepackage{graphicx}
\usepackage{enumerate}

\ifpdf\DeclareGraphicsRule{*}{mps}{*}{}\fi

\empaddtoTeX{\usepackage{amsmath}}
\empprelude{input boxes; input theory}

% skip for paragraphs, don't indent
\parskip 6pt plus 1pt
\parindent=0pt
\raggedbottom
\newenvironment{indentlist}{\begin{list}{}{\addtolength{\itemsep}{0.5\baselineskip}}}{\end{list}}

\begin{document}
\begin{empfile}

\begin{center}
\textbf{\Large CS 3530: Assignment 1f} \\[2mm]
Fall 2024
\end{center}

\raggedright

\section*{Exercise 1.29b (10 points)}

\subsection*{Problem}

Use the pumping lemma to show that the following languages are not regular.
\begin{enumerate}
\item[\bfseries b.] $A_2=\{www:w\in\{a,b\}^*\}$
\end{enumerate}

\subsection*{Solution}

%% \section*{Problem 1.33 (0 points) \emph{not required}}

%% \subsection*{Problem}

%% \newcommand{\col}[2]{\genfrac{[}{]}{0pt}{}{\,#1\,}{\,#2\,}}
%% Let
%% $$ \Sigma_2=\left\{\col{0}{0},\col{0}{1},\col{1}{0},\col{1}{1}\right\}. $$
%% Here, $\Sigma_2$ contains all columns of $0$s and $1$s of height
%% two. A string of symbols in $\Sigma_2$ gives two rows of $0$s and
%% $1$s. Consider each row to be a binary number and let
%% $$ C=\{w\in\Sigma_2^*:\text{ the bottom row of }w\text{ is three times the top row}\}$$
%% For example, $\col{0}{0}\col{0}{1}\col{1}{1}\col{0}{0}\in C$, but
%% $\col{0}{1}\col{0}{1}\col{1}{1}\notin C$. Show that $C$ is regular.
%% (You may assume the result claimed in Problem~1.31.)

%% \subsection*{Solution}

% Note: to draw the [0,1] columns in a diagram, use this:
%
%   picture oo, ol, lo, ll;
%   oo = btex $\genfrac{[}{]}{0pt}{}{\,0\,}{\,0\,}$ etex;
%   ol = btex $\genfrac{[}{]}{0pt}{}{\,0\,}{\,1\,}$ etex;
%   lo = btex $\genfrac{[}{]}{0pt}{}{\,1\,}{\,0\,}$ etex;
%   ll = btex $\genfrac{[}{]}{0pt}{}{\,1\,}{\,1\,}$ etex;
%
% Then you can use these as regular labels, e.g.:
%
%   edge(q0,q1,curve,ol);
%
% (0 and 1 are not legal variable names, so I used o and l instead)


\section*{Problem 1.46c (10 points)}

\subsection*{Problem}

Prove that the following languages are not regular. You may use the
pumping lemma and the closure of the class of regular languages
under union, intersection, and complement.

\begin{enumerate}
\item[\bfseries c.] $\{w:w\in\{0,1\}^*$ is not a
palindrome$\}$\footnote{A \textit{\textbf{palindrome}} is a string
that reads the same forward and backward.}
\end{enumerate}

\subsection*{Solution}

\end{empfile}
\immediate\write18{mpost -tex=latex \jobname}
\end{document}
