InitHEADmain

8 files changed, 430 insertions, 0 deletions

diff --git a/Homework/cs5000/midterm/cs5000_midterm_01.pdf b/Homework/cs5000/midterm/cs5000_midterm_01.pdf
new file mode 100644
index 0000000..fd2ea3c
--- /dev/null
+++ b/Homework/cs5000/midterm/cs5000_midterm_01.pdf
diff --git a/Homework/cs5000/midterm/img/6b.png b/Homework/cs5000/midterm/img/6b.png
new file mode 100644
index 0000000..aec6bad
--- /dev/null
+++ b/Homework/cs5000/midterm/img/6b.png
diff --git a/Homework/cs5000/midterm/img/7.png b/Homework/cs5000/midterm/img/7.png
new file mode 100644
index 0000000..7abf636
--- /dev/null
+++ b/Homework/cs5000/midterm/img/7.png
diff --git a/Homework/cs5000/midterm/img/p6.png b/Homework/cs5000/midterm/img/p6.png
new file mode 100644
index 0000000..f1a268a
--- /dev/null
+++ b/Homework/cs5000/midterm/img/p6.png
diff --git a/Homework/cs5000/midterm/img/prob_2_parse_tree.png b/Homework/cs5000/midterm/img/prob_2_parse_tree.png
new file mode 100644
index 0000000..5600029
--- /dev/null
+++ b/Homework/cs5000/midterm/img/prob_2_parse_tree.png
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$
diff --git a/Homework/cs5000/midterm/midterm.pdf b/Homework/cs5000/midterm/midterm.pdf
new file mode 100644
index 0000000..29aa5bc
--- /dev/null
+++ b/Homework/cs5000/midterm/midterm.pdf
diff --git a/Homework/cs5000/midterm/midterm.tex b/Homework/cs5000/midterm/midterm.tex
new file mode 100644
index 0000000..20335ef
--- /dev/null
+++ b/Homework/cs5000/midterm/midterm.tex
@@ -0,0 +1,242 @@
+% Created 2023-10-06 Fri 20: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 (A02364151)}
+\date{\today}
+\title{Theory of Computability Midterm 1}
+\hypersetup{
+ pdfauthor={Elizabeth Hunt (A02364151)},
+ pdftitle={Theory of Computability Midterm 1},
+ pdfkeywords={},
+ pdfsubject={},
+ pdfcreator={Emacs 28.2 (Org mode 9.7-pre)}, 
+ pdflang={English}}
+\begin{document}
+
+\maketitle
+\setlength\parindent{20pt}
+
+\section{Problem 1}
+\label{sec:orgb0784e8}
+\subsection{Stage 1}
+\label{sec:org855b93a}
+We skip Stage 1; there are no productions in the form \(A \rightarrow BC\) or \(A \rightarrow s\).
+
+\(P' = \{ \}\)
+
+\subsection{Stage 2}
+\label{sec:org325eccc}
+\(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 \}\)
+
+\subsection{Stage 3}
+\label{sec:orgeecaa22}
+
+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*}
+
+\section{Problem 2}
+\label{sec:orgde63c33}
+
+\begin{center}
+\includegraphics[width=150px]{./img/prob_2_parse_tree.png}
+\end{center}
+
+Yes, we can recognize the string by this derivation.
+
+\section{Problem 3}
+\label{sec:org4d6de8f}
+
+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\textsubscript{0}, \(\delta\), etc\ldots{}) 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{verbatim}
+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{verbatim}
+
+
+\section{Problem 4}
+\label{sec:orgf8f3fbd}
+We can construct a CFG:
+
+\(S \rightarrow aSbbb | abbb\)
+
+Which we convert to a stack machine:
+
+\begin{center}
+\begin{tabular}{lll}
+read & pop & push\\[0pt]
+\(\epsilon\) & S & aSbbb\\[0pt]
+\(\epsilon\) & S & abbb\\[0pt]
+a & a & \(\epsilon\)\\[0pt]
+b & b & \(\epsilon\)\\[0pt]
+\end{tabular}
+\end{center}
+
+\(M = (\{a, b, S\}, \{a, b\}, S, \delta)\)
+
+where
+
+\begin{enumerate}
+\item \(\delta(\epsilon, S) = \{aSbbb, abbb\}\)
+\item \(\delta(a, a) = \{ \epsilon \}\)
+\item \(\delta(b, b) = \{ \epsilon \}\)
+\end{enumerate}
+
+\section{Problem 5}
+\label{sec:org0f801f2}
+
+\begin{enumerate}
+\item \(S \rightarrow 0 | 0T | 1T\)
+\item \(T \rightarrow 1S | 0S\)
+\end{enumerate}
+
+Is a right linear grammar, and is thus regular.
+
+\section{Problem 6}
+\label{sec:org690d7be}
+\subsection{One}
+\label{sec:orgc0da8de}
+\begin{center}
+\includegraphics[width=200px]{./img/p6.png}
+\end{center}
+
+\begin{itemize}
+\item \(Q = \{p_0, p_1\}\)
+\item \(F = \{p_1\}\)
+\item \(\Sigma = \{1\}\)
+\item \(S = p_0\)
+\item \(\delta(p_0, 1) = p_1\)
+\item \(\delta(p_1, 1) = p_0\)
+\end{itemize}
+
+\subsection{Two}
+\label{sec:org0e05810}
+
+\begin{center}
+\includegraphics[width=200px]{./img/6b.png}
+\end{center}
+
+\begin{itemize}
+\item \(Q = \{p_0, p_1, p_2, p_3, p_4, p_5\}\)
+\item \(F = \{p_2, p_4, p_6\}\)
+\item \(\Sigma = \{a, b\}\)
+\item \(S = p_0\)
+\item \(\delta(p_0, a) = p_1\)
+\item \(\delta(p_0, b) = p_3\)
+\item \(\delta(p_1, a) = p_6\)
+\item \(\delta(p_1, b) = p_2\)
+\item \(\delta(p_2, b) = p_5\)
+\item \(\delta(p_5, b) = p_2\)
+\item \(\delta(p_3, b) = p_4\)
+\item \(\delta(p_4, b) = p_3\)
+\item \(\delta(p_3, a) = \delta(p_4, a) = \delta(p_2, a) = \delta(p_5, a) = \emptyset\)
+\end{itemize}
+
+\section{Problem 7}
+\label{sec:org4149a63}
+\begin{center}
+\includegraphics[width=200px]{./img/7.png}
+\end{center}
+
+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:
+
+\begin{itemize}
+\item \(Q = \{q_0, q_1, q_2, q_3, q_4\}\)
+\item \(F = \{q_4\}\)
+\item \(\Sigma = \{a, b\}\)
+\item \(S = q_0\)
+\item \(\delta(q_0, a) = q_1\)
+\item \(\delta(p_1, a) = q_2\)
+\item \(\delta(q_2, a) = q_2\)
+\item \(\delta(q_2, b) = q_3\)
+\item \(\delta(q_3, b) = q_4\)
+\item \(\delta(p_4, b) = q_4\)
+\item \(\delta(q_0, b) = \delta(q_1, b) = \delta(q_3, a) = \delta(p_4, a) = \emptyset\)
+\end{itemize}
+\end{document}
\ No newline at end of file