diff options
Diffstat (limited to 'Homework/cs5000/midterm/midterm.tex')
| -rw-r--r-- | Homework/cs5000/midterm/midterm.tex | 242 |
1 files changed, 242 insertions, 0 deletions
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 |