From 6bf4b90c90f15f4ab60833bddf5b5756d1a6b1f6 Mon Sep 17 00:00:00 2001
From: Elizabeth Alexander Hunt <me@liz.coffee>
Date: Thu, 2 Jul 2026 11:55:17 -0700
Subject: Init

---
 Homework/cs5000/midterm/midterm.tex | 242 ++++++++++++++++++++++++++++++++++++
 1 file changed, 242 insertions(+)
 create mode 100644 Homework/cs5000/midterm/midterm.tex

(limited to 'Homework/cs5000/midterm/midterm.tex')

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
-- 
cgit v1.3

