%
% Assignment 1c for CS3530 Computational Theory:
% Finite Automata
% Fall 2023
%
% 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}

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

\empprelude{input boxes; input theory}

% skip for paragraphs, don't indent
\addtolength{\parskip}{0.5\baselineskip}
\parindent=0pt

\begin{document}
\begin{empfile}

\begin{center}
\textbf{\Large CS 3530: Assignment 1c} \\[2mm]
Fall 2023

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

\raggedright

\section*{Exercise 1.15 (6 points)}

\subsection*{Problem}

Give a counterexample to show that the following construction fails
to prove Theorem~1.49, the closure of the class of regular languages
under the star operation.%
\footnote{In other words, you must present a finite automaton,
$N_1$, for which the constructed automaton $N$ does not recognize
the star of $N_1$'s language.}
Let $N_1=(Q_1,\Sigma,\delta_1,q_1,F_1)$ recognize $A_1$. Construct
$N=(Q_1,\Sigma,\delta,q_1,F)$ as follows. $N$ is supposed to
recognize $A^*_1$.

\begin{enumerate}
\renewcommand{\labelenumi}{\alph{enumi}}
\item The states of $N$ are the states of $N_1$.
\item The start state of $N$ is the same as the start state of $N_1$.
\item $F=\{q_1\}\cup F_1$.

The accept states $F$ are the old accept states plus its start state.
\item Define $\delta$ so that for any $q\in Q$ and any
$a\in\Sigma_\varepsilon$,
$$
\delta(q,a)=
\begin{cases}
\delta_1(q,a) & q\notin F_1\text{ or }a\neq\varepsilon \\
\delta_1(q,a)\cup\{q_1\} & q\in F_1\text{ and }a=\varepsilon.
\end{cases}
$$
\end{enumerate}
(Suggestion: Show this construction graphically, as in Figure~1.50.)

\subsection*{Solution}

\section*{Problem 1.60 (7 points)}

\subsection*{Problem}

Let $\Sigma=\{a,b\}$. For each $k\geq 1$, let $C_k$ be the language
consisting of all strings that contain an $a$ exactly $k$ places
from the right-hand end. Thus $C_k=\Sigma^*a\Sigma^{k-1}$. Describe
an NFA with $k+1$ states that recognizes $C_k$, both in terms of a
state diagram and a formal description.

\subsection*{Solution}

\section*{Problem 1.62 (7 points)}

\subsection*{Problem}

Let $\Sigma=\{a,b\}$. For each $k\geq 1$, let $D_k$ be the language
consisting of all strings that have at least one $a$ among the last
$k$ symbols. Thus $D_k=\Sigma^*a(\Sigma\cup\varepsilon)^{k-1}$.
Describe a DFA with at most $k+1$ states that recognizes $D_k$, both
in terms of a state diagram and a formal description.

\subsection*{Solution}

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