% 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}