<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass{2800hw}
\usepackage{amsmath,amssymb,latexsym}
\usepackage{verbatim}
\usepackage{utf8}

\usepackage{tikz}
\usetikzlibrary{automata}
\usetikzlibrary{positioning}
\usetikzlibrary{fit}
\usetikzlibrary{calc}
\usetikzlibrary{shapes.misc}

\tikzset{machine/.style = {row sep=3em, column sep=3em}}
\tikzset{initial text = {}}

\topic{Automata and Regular Expressions}
\homework{8}

\begin{document}
\maketitle

\begin{exercises}
\item There can be different automata that accept the same language.  In this
problem you will walk through an algorithm that converts a given DFA to an
equivalent DFA with the minimal number of states.  The key idea is that we want
to consolidate ``duplicate'' states; i.e. states that ``behave the same''.

Some of these questions refer to the following machine $M_{example}$:
\begin{center}
\begin{tikzpicture}

\matrix[machine] (M) {
 &amp;
 &amp;
 &amp;
\node[state] (q4) {$q_4$}; &amp;
 \\

\node[state,initial]   (q1) {$q_1$}; &amp;
\node[state,accepting] (q2) {$q_2$}; &amp;
\node[state]           (q5) {$q_5$}; &amp;
 &amp;
\node[state]           (q7) {$q_7$}; \\

 &amp;
\node[state]           (q3) {$q_3$}; &amp;
\node[state,accepting] (q6) {$q_6$}; &amp;
 &amp;
 \\
};

\path[-&gt;]
  (q1) edge[loop below] node[below]       {$0$} (q1)
  (q1) edge[bend left]  node[above]       {$1$} (q2)
  (q2) edge[bend left]  node[above left]  {$0$} (q4)
  (q2) edge             node[above]       {$1$} (q5)
  (q3) edge             node[above left]  {$0$} (q5)
  (q3) edge             node[left]        {$1$} (q2)
  (q4) edge[bend left]  node[above right] {$0,1$} (q7)
  (q5) edge             node[below right] {$0$} (q3)
  (q5) edge             node[right]       {$1$} (q6)
  (q6) edge[bend right] node[below right] {$0$} (q7)
  (q6) edge             node[below]       {$1$} (q3)
  (q7) edge[bend left]  node[below left]  {$0,1$} (q4)
;

\end{tikzpicture}
\end{center}


\begin{enumerate}
\item We need to consider the language of a machine starting from a given state.
Let $L(M,q)$ be the set of strings that $M$ would accept if it started in state
$q$.  Write down a formal definition for $L(M,q)$ in terms of the extended
transition function.

\item We can define an equivalence relation $\sim$ to capture the idea that two
states ``behave the same'': we say that $q_1 \sim q_2$ if $L(M,q_1) = L(M,q_2)$.
Prove that $\sim$ is an equivalence relation.

\item We now want to create a new machine $M'$ such that $L(M') = L(M)$.  The
set of states of $M'$ will be the quotient of the states of $M$ by the
equivalence relation $\sim$ (in other words, $Q' = Q / \sim$).  Explicitly
write down the set $Q'$ for the machine $M_{example}$ depicted above.
(\emph{Hint: there are three elements of $Q'$, each of which is a set}).

\item
We can define the transition function $\delta'$ for $M'$ as follows: given
an equivalence class $q' \in Q'$, we can choose a representative element $q$ of $q'$ and let
$\delta'(q', a)$ be the equivalence class of $\delta(q,a)$.

This may be ambiguous, because there may be many different representatives of
the equivalence class $q'$.  Show that the function is in fact well defined, by
showing that if we make two different choices of $q$ we still get the same
value $\delta'(q',a)$.

\item Write down a general expression for the initial state and the set of
final states of $M'$.

\item Draw $M'$ for $M_{example}$.
\end{enumerate}

\end{exercises}

\end{document}
</pre></body></html>