%
% Assignment 1h 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 1h} \\[2mm]
Fall 2024
\end{center}

\raggedright

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

\subsection*{Problem}

Prove that 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 b.] $\{0^n1^m0^n | m,n \ge 0\}$
\end{enumerate}

\subsection*{Solution}


\section*{Problem 1.53 (10 points)}

\subsection*{Problem}

Let $\Sigma = \{0,1,+,=\}$ and \textsc{ADD}$ = \{ x=y+z| x,y,z $ are binary integers, and $x$ is the sum of $y$ and $z \}$.  Show that \textsc{ADD} is not regular.

\subsection*{Solution}

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