#+TITLE: HW 02
#+AUTHOR: Elizabeth Hunt
#+STARTUP: entitiespretty fold inlineimages
#+LATEX_HEADER: \notindent \notag  \usepackage{amsmath} \usepackage[a4paper,margin=1in,portrait]{geometry}
#+LATEX: \setlength\parindent{0pt}
#+OPTIONS: toc:nil

* Question One
** Partition Refinement
{ {q_0, q_1, q_3}, {q_2, q_4} }

S_1 = {(q_0, q_1), (q_0, q_3), (q_1, q_3)}
S_2 = {(q_2, q_4)}

\delta(q_0, 1) = q_3 \in S_1
\delta(q_1, 1) = q_4 \in S_2

(q_0, q_1) need to be split

\delta(q_0, 0) = q_1 \in S_1
\delta(q_3, 0) = q_2 \in S_2

(q_1, q_2) need to be split

\forall x \in \Sigma, \delta(q_1, x) = \delta(q_3, x)
so {q_1, q_3} does not need to be split

In S_2, \delta(q_2, 0) \in S_1 and \delta(q_4, 0) \in S_2, thus need to be split

Finally, the refined partitions are {{q_0}, {q_1, q_3}, {q_2}, {q_4}}

** Minimization
| a \in \Sigma | {q_0}     | {q_1, q_3} | {q_2}     | {q_4} |
|     0 | {q_1, q_3} | {q_2}     | {q_1, q_3} | {q_4} |
|     1 | {q_1, q_3} | {q_4}     | {q_4}     | {q_4} |

with d_0 = {q_0}, d_1 = {q_1, q_3}, d_2 = {q_2} and d_3 = {q_4}

#+attr_latex: :width 350px
[[./img/min_dfa.png]]

* Question Two
See attached python