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
|
#+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
* Problem 1
** Part 1
$L(M) = \{ x | x \in \{ a \}^{*} \} \cup \{ x | x \in \{ b \}^{*} \} \cup \{ x | x \in \{ c \}^{*} \}$
** Part 2
#+attr_latex: :width 300px
[[./img/p01_02.png]]
$Q = {q_0, q_1, q_2, q_3}$
$\Sigma = {a, b, c}$
$F = {q_1, q_2, q_3}$
$\delta(q_0, a) = {q_1}, \delta(q_1, a) = {q_1}, \delta(q_0, b) = {q_2}, \delta(q_2, b) = {q_2}, \delta(q_0, c) = {q_3}, \delta(q_3, c) = c$
* Problem 2
** Work
| subset | 0 | 1 |
| {q_0} | {q_0, q_1} | {q_1} |
| {q_1} | {q_2} | {q_2} |
| {q_2} | {q_2} | {q_2} |
| {q_0, q_1} | {q_0, q_1} \cup {q_2} | {q_1} \cup {q_2} |
| {q_0, q_1, q_2} | {q_0, q_1} \cup {q_2} \cup {q_2} | {q_1} \cup {q_2} \cup {q_2} |
| {q_1, q_2} | {q_2} \cup {q_2} | {q_2} \cup {q_2} |
** Solution
#+attr_latex: :width 300px
[[./img/p02.png]]
$Q_D = \{q_0, q_1, q_2, q_3, q_4, q_5\}$
$\Sigma = \{0, 1\}$
$F_D = \{q_1, q_2, q_4, q_5\}$
$\delta_D(q_0, 0) = q_1$
$\delta_D(q_0, 1) = q_2$
$\delta_D(q_1, 0) = q_5$
$\delta_D(q_1, q) = q_4$
$\delta_D(q_2, 0) = \delta_D(q_2, 1) = q_3$
$\delta_D(q_3, 0) = \delta_D(q_3, 1) = q_3$
$\delta_D(q_4, 0) = \delta_D(q_4, 1) = q_4$
$\delta_D(q_5, 0) = q_5$
$\delta_D(q_5, 1} = q_4$
* Problem 3
See attached python
|
