%
% Assignment 2a for CS3530 Computational Theory:
% Regular Expressions
% 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

\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 1d} \\[2mm]
Fall 2024

\emph{Your Name Here}
\end{center}

\raggedright

\section*{Exercise 1.12 (6 points)}

\subsection*{Problem}

Let $D=\{w|w$ contains an even number of $a$'s and an odd number of
$b$'s and does not contain the substring $ab\}$. Give a DFA with
five states that recognizes $D$ and a regular expression that
generates $D$. (Suggestion: Describe $D$ more simply).

\subsection*{Solution}

\section*{Exercise 1.18 (14 points)}

\subsection*{Problem}

Give regular expressions generating the languages of Exercise~1.6.

\begin{enumerate}[\bfseries a.]
\item $\{w| w$ begins with a $1$ and ends with a $0\}$

\textbf{Solution}

\item $\{w| w$ contains at least three $1$s$\}$

\textbf{Solution}

\item $\{w| w$ contains the substring $0101$, i.e., $w=x0101y$ for
some $x$ and $y\}$

\textbf{Solution}

\item $\{w| w$ has length at least $3$ and its third symbol is a $0\}$

\textbf{Solution}

\item $\{w| w$ starts with $0$ and has odd length, or starts with
$1$ and has even length$\}$

\textbf{Solution}

\item $\{w| w$ doesn't contain the substring $110\}$

\textbf{Solution}

\item $\{w|$ the length of $w$ is at most $5\}$

\textbf{Solution}

\item $\{w| w$ is any string except $11$ and $111\}$

\textbf{Solution}

\item $\{w|$ every odd position of $w$ is a $1\}$

\textbf{Solution}

\item $\{w| w$ contains at least two $0$s and at most one $1\}$

\textbf{Solution}

\item $\{\varepsilon, 0\}$

\textbf{Solution}

\item $\{w| w$ contains an even number of $0$s, or contains exactly
two $1$s$\}$

\textbf{Solution}

\item The empty set

\textbf{Solution}

\item All strings except the empty string

\textbf{Solution}
\end{enumerate}

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

%% \subsection*{Problem}

%% For any string $w=w_1w_2\cdots w_n$, the \textbf{\textit{reverse}}
%% of $w$, written $w^\mathcal{R}$, is the string $w$ in reverse order,
%% $w_n\cdots w_2w_1$. For any language $A$, let
%% $A^\mathcal{R}=\{w^\mathcal{R}: w\in A\}$. Show that if $A$ is
%% regular, so is $A^\mathcal{R}$.

%% \subsection*{Solution}

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