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
|
#+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
|
