InitHEADmain

1 files changed, 188 insertions, 0 deletions

diff --git a/Homework/cs5000/midterm/midterm.org b/Homework/cs5000/midterm/midterm.org
new file mode 100644
index 0000000..1ad41f7
--- /dev/null
+++ b/Homework/cs5000/midterm/midterm.org
@@ -0,0 +1,188 @@
+#+TITLE: Theory of Computability Midterm 1
+#+AUTHOR: Elizabeth Hunt (A02364151)
+#+STARTUP: entitiespretty fold inlineimages
+#+LATEX_HEADER: \notindent \notag  \usepackage{amsmath} \usepackage[a4paper,margin=1in,portrait]{geometry}
+#+LATEX: \setlength\parindent{20pt}
+#+OPTIONS: toc:nil
+
+* Problem 1
+** Stage 1
+We skip Stage 1; there are no productions in the form $A \rightarrow BC$ or $A \rightarrow s$.
+
+$P' = \{ \}$
+
+** Stage 2
+$P' = \{ C_a \rightarrow a , C_b \rightarrow b, C_c \rightarrow c, C_d \rightarrow d \}$
+
+And our new productions are $\{ S \rightarrow C_a S C_b C_b , S \rightarrow C_a S C_a , S \rightarrow C_b S C_a C_a , S \rightarrow C_b S C_b , S \rightarrow C_c C_d \}$
+
+** Stage 3
+
+We replace $S \rightarrow C_a S C_b C_b$ with $\{ S \rightarrow C_a D_1 , D_1 \rightarrow S D_2 , D_2 \rightarrow C_b C_b \}$
+
+We replace $S \rightarrow C_a S C_a$ with $\{ S \rightarrow C_a D_3, D_3 \rightarrow S C_a \}$
+
+We replace $S \rightarrow C_b S C_a C_a$ with $\{ S \rightarrow C_b D_4 , D_4 \rightarrow S D_5 , D_5 \rightarrow C_a C_a \}$
+
+We replace $S \rightarrow C_b S C_b$ with $\{ S \rightarrow C_b D_6 , D_6 \rightarrow S C_b \}$.
+
+We add $S \rightarrow C_c C_d$ as it is in CNF already.
+
+Thus,
+
+\begin{align*}
+P' &=  \{ C_a \rightarrow a , C_b \rightarrow b, C_c \rightarrow c, C_d \rightarrow d \} \\
+   & \cup \{ S \rightarrow C_a D_1 , D_1 \rightarrow S D_2 , D_2 \rightarrow C_b C_b \} \\
+   & \cup \{ S \rightarrow C_a D_3, D_3 \rightarrow S C_a \} \\
+   & \cup \{ S \rightarrow C_b D_4 , D_4 \rightarrow S D_5 , D_5 \rightarrow C_a C_a \} \\
+   & \cup \{ S \rightarrow C_b D_6 , D_6 \rightarrow S C_b \} \\
+   & \cup \{ S \rightarrow C_c C_d \}
+\end{align*}
+
+* Problem 2
+
+#+attr_latex: :width 150px
+[[./img/prob_2_parse_tree.png]]
+
+Yes, we can recognize the string by this derivation.
+
+* Problem 3
+
+Because strings in $L(M_1)$ and $L(M_2)$ are recognized by Discrete Finite Automata,
+they must be regular languages.
+
+By the Myhill-Nerode theorem, if $L$ is a regular language it can be recognized by a unique DFA
+with a minimal number of states. In other words, we know that if two DFA recognize
+the same language, they must have the same minimal DFA.
+
+Let $\text{minimize}(D)$ be the minimization algorithm given in Lecture 04 returning a deterministic
+set of states.
+
+Then, we know $M_1$ is equivalent to $M_2$ when $\text{minimize}(M_1)$ is congruent to
+$\text{minimize}(M_2)$. This is only true when all descriptors (\Sigma, q_0, \delta, etc...) are also
+equivalent.
+
+In the below pseduo code we just check the equivalence of the set of states, alphabet, and start
+state. Then we perform a search to see if $(\delta_1) = M_1$ is $\subseteq$ of $(\delta_2) = M_2$ and
+$\delta_2 \subseteq \delta_1$, and if both are true, then $\delta_1 = \delta_2$.
+
+If all are equivalent, then the languages recognize the same strings!
+
+#+BEGIN_SRC python
+   def minimize(dfa):
+       minimized = dfa.copy()
+       # ... mutate minimized according to minimize()
+       return minimized
+
+   def delta_subseteq(start_state, sigma, delta1, delta2):
+       visited = set()
+       for transition in delta2.keys():
+           if transition not in delta1 or \
+                  delta1[transition] != delta2[transition]:
+               return False
+       return True
+
+   def equivalent(m1, m2):
+       minimized_m1 = minimize(m1)
+       minimized_m2 = minimize(m2)
+       if minimized_m1.Q != minimized_m2.Q or \
+              minimzed_m1.sigma != minimized_m2.sigma or \
+              minimized_m1.q0 != minimized_m2.q0 or \
+              minimized_m1.F != minimized_m2.F:
+           return False
+
+       m2_delta_includes_m1_delta = delta_subseteq(minimized_m1.q0, \
+                                                   minimized_m1.sigma, \
+                                                   minimized_m1.delta, \
+                                                   minimized_m2.delta)
+
+       m1_delta_includes_m2_delta = delta_subseteq(minimized_m2.q0, \
+                                                   minimized_m2.sigma, \
+                                                   minimized_m2.delta, \
+                                                   minimized_m1.delta)
+
+       return m2_delta_includes_m1_delta and m1_delta_includes_m2_delta
+#+END_SRC
+
+
+* Problem 4
+We can construct a CFG:
+
+$S \rightarrow aSbbb | abbb$
+
+Which we convert to a stack machine:
+
+| read | pop | push  |
+| \epsilon    | S   | aSbbb |
+| \epsilon    | S   | abbb  |
+| a    | a   | \epsilon     |
+| b    | b   | \epsilon     |
+
+$M = (\{a, b, S\}, \{a, b\}, S, \delta)$
+
+where
+
+1. $\delta(\epsilon, S) = \{aSbbb, abbb\}$
+2. $\delta(a, a) = \{ \epsilon \}$
+3. $\delta(b, b) = \{ \epsilon \}$
+
+* Problem 5
+
+1. $S \rightarrow 0 | 0T | 1T$
+2. $T \rightarrow 1S | 0S$
+
+Is a right linear grammar, and is thus regular.
+
+* Problem 6
+** One
+#+attr_latex: :width 200px
+[[./img/p6.png]]
+
++ $Q = \{p_0, p_1\}$
++ $F = \{p_1\}$
++ $\Sigma = \{1\}$
++ $S = p_0$
++ $\delta(p_0, 1) = p_1$
++ $\delta(p_1, 1) = p_0$
+
+** Two
+
+#+attr_latex: :width 200px
+[[./img/6b.png]]
+
++ $Q = \{p_0, p_1, p_2, p_3, p_4, p_5\}$
++ $F = \{p_2, p_4, p_6\}$
++ $\Sigma = \{a, b\}$
++ $S = p_0$
++ $\delta(p_0, a) = p_1$
++ $\delta(p_0, b) = p_3$
++ $\delta(p_1, a) = p_6$
++ $\delta(p_1, b) = p_2$
++ $\delta(p_2, b) = p_5$
++ $\delta(p_5, b) = p_2$
++ $\delta(p_3, b) = p_4$
++ $\delta(p_4, b) = p_3$
++ $\delta(p_3, a) = \delta(p_4, a) = \delta(p_2, a) = \delta(p_5, a) = \emptyset$
+
+* Problem 7
+#+attr_latex: :width 200px
+[[./img/7.png]]
+
+Because the magnitude of each element in the range of $\delta$ is 1 then, intuitively, if we follow
+the subset construction algorithm with queue optimization we will only end up with new states
+identical to the ones present in the current NFA (i.e. we will visit no elements of the powerset
+whose magnitude is greater than one also).
+
+Thus the DFA is:
+
++ $Q = \{q_0, q_1, q_2, q_3, q_4\}$
++ $F = \{q_4\}$
++ $\Sigma = \{a, b\}$
++ $S = q_0$
++ $\delta(q_0, a) = q_1$
++ $\delta(p_1, a) = q_2$
++ $\delta(q_2, a) = q_2$
++ $\delta(q_2, b) = q_3$
++ $\delta(q_3, b) = q_4$
++ $\delta(p_4, b) = q_4$
++ $\delta(q_0, b) = \delta(q_1, b) = \delta(q_3, a) = \delta(p_4, a) = \emptyset$