1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
% Created 2023-09-20 Wed 15:58
% Intended LaTeX compiler: pdflatex
\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{longtable}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{capt-of}
\usepackage{hyperref}
\notindent \notag \usepackage{amsmath} \usepackage[a4paper,margin=1in,portrait]{geometry}
\author{Elizabeth Hunt}
\date{\today}
\title{HW 02}
\hypersetup{
pdfauthor={Elizabeth Hunt},
pdftitle={HW 02},
pdfkeywords={},
pdfsubject={},
pdfcreator={Emacs 28.2 (Org mode 9.7-pre)},
pdflang={English}}
\begin{document}
\maketitle
\setlength\parindent{0pt}
\section{Question One}
\label{sec:org859695d}
\subsection{Partition Refinement}
\label{sec:org55dda6e}
\{ \{q\textsubscript{0}, q\textsubscript{1}, q\textsubscript{3}\}, \{q\textsubscript{2}, q\textsubscript{4}\} \}
S\textsubscript{1} = \{(q\textsubscript{0}, q\textsubscript{1}), (q\textsubscript{0}, q\textsubscript{3}), (q\textsubscript{1}, q\textsubscript{3})\}
S\textsubscript{2} = \{(q\textsubscript{2}, q\textsubscript{4})\}
\(\delta\)(q\textsubscript{0}, 1) = q\textsubscript{3} \(\in\) S\textsubscript{1}
\(\delta\)(q\textsubscript{1}, 1) = q\textsubscript{4} \(\in\) S\textsubscript{2}
(q\textsubscript{0}, q\textsubscript{1}) need to be split
\(\delta\)(q\textsubscript{0}, 0) = q\textsubscript{1} \(\in\) S\textsubscript{1}
\(\delta\)(q\textsubscript{3}, 0) = q\textsubscript{2} \(\in\) S\textsubscript{2}
(q\textsubscript{1}, q\textsubscript{2}) need to be split
\(\forall\) x \(\in\) \(\Sigma\), \(\delta\)(q\textsubscript{1}, x) = \(\delta\)(q\textsubscript{3}, x)
so \{q\textsubscript{1}, q\textsubscript{3}\} does not need to be split
In S\textsubscript{2}, \(\delta\)(q\textsubscript{2}, 0) \(\in\) S\textsubscript{1} and \(\delta\)(q\textsubscript{4}, 0) \(\in\) S\textsubscript{2}, thus need to be split
Finally, the refined partitions are \{\{q\textsubscript{0}\}, \{q\textsubscript{1}, q\textsubscript{3}\}, \{q\textsubscript{2}\}, \{q\textsubscript{4}\}\}
\subsection{Minimization}
\label{sec:org870d4d3}
\begin{center}
\begin{tabular}{rllll}
a \(\in\) \(\Sigma\) & \{q\textsubscript{0}\} & \{q\textsubscript{1}, q\textsubscript{3}\} & \{q\textsubscript{2}\} & \{q\textsubscript{4}\}\\[0pt]
0 & \{q\textsubscript{1}, q\textsubscript{3}\} & \{q\textsubscript{2}\} & \{q\textsubscript{1}, q\textsubscript{3}\} & \{q\textsubscript{4}\}\\[0pt]
1 & \{q\textsubscript{1}, q\textsubscript{3}\} & \{q\textsubscript{4}\} & \{q\textsubscript{4}\} & \{q\textsubscript{4}\}\\[0pt]
\end{tabular}
\end{center}
with d\textsubscript{0} = \{q\textsubscript{0}\}, d\textsubscript{1} = \{q\textsubscript{1}, q\textsubscript{3}\}, d\textsubscript{2} = \{q\textsubscript{2}\} and d\textsubscript{3} = \{q\textsubscript{4}\}
\begin{center}
\includegraphics[width=350px]{./img/min_dfa.png}
\end{center}
\section{Question Two}
\label{sec:orga1d2018}
See attached python
\end{document}
|
