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/hw06/hw06.tex | 220 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 220 insertions(+)
 create mode 100644 Homework/cs5000/hw06/hw06.tex

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

diff --git a/Homework/cs5000/hw06/hw06.tex b/Homework/cs5000/hw06/hw06.tex
new file mode 100644
index 0000000..3d0af5f
--- /dev/null
+++ b/Homework/cs5000/hw06/hw06.tex
@@ -0,0 +1,220 @@
+% Created 2023-11-02 Thu 12:14
+% 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{HW 06}
+\hypersetup{
+ pdfauthor={Elizabeth Hunt (A02364151)},
+ pdftitle={HW 06},
+ pdfkeywords={},
+ pdfsubject={},
+ pdfcreator={Emacs 28.2 (Org mode 9.7-pre)}, 
+ pdflang={English}}
+\begin{document}
+
+\maketitle
+\setlength\parindent{20pt}
+
+\section{Problem One}
+\label{sec:orgf4c2128}
+\subsection{1 - \{ a\textsuperscript{i} b\textsuperscript{j} c\textsuperscript{k} | i > j > k \}}
+\label{sec:orgd221679}
+We assume that there exists a Context Free Language, \(L\) such that \(L = { a^i b^j c^k | i > j > k }\).
+Then by the Pumping Lemma for Context Free Languages, for each \(z \in L\) of sufficient length \(n\) we can
+split \(z\) into the sequence of substrings \(uvwxy\) with \(|vx| \geq 1\) and \(|vwx| \le n\). Any such "pumped"
+string \(uv^i w x^i y \forall i \ge 0\) is also in \(L\).
+
+Consider the string \(a^{n+2} b^{n+1} c^{}^n \in L\) which is always longer than \(n\) (the integer of the Pumping Lemma)
+so it is of sufficient length. Splitting this up according to the aforementioned Lemma, we know
+\(|vwx| \le n\) and thus the string \(vx\) contains either all of one letter or two different letters.
+
+If \(vx\) contains only \(a\)'s or \(b\)'s then we can "pump" \(vx\) 0 times to produce \(z^* = u v^0 w x^0 y\) and
+since \(|vx| \geq 1\) then we lose \(p \geq 1\) \(a\)'s or \(b\)'s. Thus, in the case of \(a\), \((n+2)-p \leq n+1\) and
+\(z^*\) is not in \(L\), and in the case of \(b\), \((n+1)-p \leq n\), with the same conclusion.
+
+If \(vx\) contains only \(c\)'s then we can "pump" \(vx\) \(n\) times to produce \(z^* = u v^n w x^n y\) at least
+\(2n\) the number of \(c's\) (which is always \(\ge n\)), and there would be equal or more \(c\)'s to
+\(b\)'s and thus \(z^* \notin L\).
+
+If \(vx\) contains both \(a\)'s and \(b\)'s then we can "pump" \(vx\) 0 times similar to the case of only \(a\)'s
+and \(b\)'s to produce a string with an equal or less number of \(b\)'s than \(c\)'s.
+
+If \(vx\) contains both \(b\)'s and \(c\)'s then we can "pump" \(vx\) \(3n\) times to come up with a string that
+will always have \(b\)'s and \(c\)'s greater or eqaul to the number of \(a\)'s.
+
+\subsection{2 - \{ a\textsuperscript{i} b\textsuperscript{j} | i = j\textsuperscript{2} \}}
+\label{sec:org5f8cc3e}
+
+We assume that there exists a Context Free Language, \(L\) such that \(L = { a^i b^j | i = j^2 }\).
+
+Then by the Pumping Lemma for Context Free Languages, for each \(z \in L\) of sufficient length \(n\) we can
+split \(z\) into the sequence of substrings \(uvwxy\) with \(|vx| \geq 1\) and \(|vwx| \le n\). Any such "pumped"
+string \(uv^i w x^i y \forall i \ge 0\) is also in \(L\).
+
+Consider the string \(a^{n^2}^{} b^{}^n \in L\) which is always longer than \(n\) (the integer of the Pumping Lemma)
+so it is of sufficient length. Splitting this up according to the aforementioned Lemma, we know
+\(|vwx| \le n\) and thus the string \(vx\) contains either all of one letter or two different letters.
+
+\begin{enumerate}
+\item If \(vx\) contains only \(a\)'s then we can "pump" \(vx\) 0 times to produce \(z^* = u v^0 w x^0 y\) and
+since \(|vx| \geq 1\) then we lose \(p \geq 1\) \(a\)'s and thus \(z^* = a^{n^2 - p} b^n \notin L\) as \(n^2 - p \ne n^2\).
+
+\item If \(vx\) contains only \(b\)'s then we can "pump" \(vx\) 2 times to produce \(z^* = u v^2 w x^2 y\) and
+since \(|vx| \geq 1\) then we add \(p \geq 2\) \(b\)'s and thus \(z^* = a^{n^2} b^{n+p} \notin L\) as \(n^2 \ne (n + p)^2\).
+
+\item If \(vx\) contains both \(b\)'s and \(a\)'s then we can prove that we can construct a number of times to pump
+such that the relationship for \(i = j^2\) cannot be satisfied:
+\begin{itemize}
+\item \(v\) must contain only \(a\)'s and \(x\) must contain only \(b\)'s; else we could pump and obtain a string
+in which the order of \(a\)'s and \(b\)'s is disrupted.
+\item Let \(y = |v|\) and \(u = |x|\) with \(1 \leq y + u \le n\) since \(|vwx| \le n\) and \(|vx| \geq 1\).
+Then we can pump \(p \geq 1\) times to create the string
+\(z^* = a^{(n^2 - y) + py} b^{(n - u) + pu} = a^{n^2 + p(y-1)} b^{n + p(u-1)}\).
+\item Then for any such \(n, u, y\) we can find a \(p\) such that
+\((n + p(u - 1))(n + p(u - 1)) = n^2 + 2pn(u-1) + p^2(u-1)^2 \neq n^2 + p(y-1)\)
+since \(u\) and \(y\) are positive.
+\end{itemize}
+\end{enumerate}
+
+\subsection{3 - \{ a\textsuperscript{i} | i is prime \}}
+\label{sec:orgc7ac705}
+
+We assume that there exists a Context Free Language, \(L\) such that \(L = { a^i b^j | i = j^2 }\).
+
+Then by the Pumping Lemma for Context Free Languages, for each \(z \in L\) of sufficient length \(n\) we can
+split \(z\) into the sequence of substrings \(uvwxy\) with \(|vx| \geq 1\) and \(|vwx| \le n\). Any such "pumped"
+string \(uv^i w x^i y \forall i \ge 0\) is also in \(L\).
+
+Consider the string \(z = a^{p(n)} \in L\) where \(p(n)\) is a function returning the first prime number greater
+than \(n\); this string is always longer than \(n\) (the integer of the Pumping Lemma) so
+it is of sufficient length. Splitting this up according to the aforementioned Lemma, we know
+\(|vwx| \le n\) and thus the string \(vx\) is made up of one or more \(a\)'s.
+
+Given \(t = |v|\) and \(u = |x|\), and \(1 \le t + u \le n\); we can simply pump \(vx\) \(p(n)\) times to obtain
+the string \(z^* = uv^{tp(n)} w x^{up(n)}y\) which is \(a^{p(n) + tp(n) + up(n)}\). And \(p(n) + tp(n) + up(n)\) is not prime
+since it can be factored into \(p(n)(1 + t + u)\); as either \(t\) or \(u\) is greater than one, then
+\(z^* \notin L\).
+
+\section{Problem Two}
+\label{sec:org0e7b7e5}
+
+\url{https://bit.ly/cs5000-simponic-hw06-p02}
+
+
+\section{Problem Three}
+\label{sec:org3b85eb1}
+
+\url{https://bit.ly/cs5000-simponic-hw06-p03}
+
+In english(ish):
+
+\begin{enumerate}
+\item If the current symbol is \(B\), move right and goto 2
+
+\item If the current symbol is \(a, b, c\), move right and goto 2. If the current symbol is \(B\), move Left and goto 3.
+If the current symbol is * we move left and goto 6.
+
+\item We're at the last \(c\) in the string. If the current symbol is \(c\) then we print \$ and go left until
+we see an \(a\). Then, move Left and go to 4.
+
+\item If the current symbol is \(b\) then we print * and go right until we see \$. At which we move left and
+goto 3. If the symbol is * then we move right and goto 5.
+
+\item If the current symbol is b, c, *, we move right and goto 5. If it's \$ we move left and goto 2 to do the next
+iteration.
+
+\item We move left until we hit \(B\) at which we move right and goto 7.
+
+\item We're now at the beginning of the \(a\)'s after replacing all \(c\)'s with \$ and \(b\)'s with *. If we read
+an \(a\) we print \(+\) and goto 8. If we see a \(-\) (which we replace \(*\)'s with), we accept.
+
+\item If the current symbol is \(+, a, *\), we move right and goto 8. If we see \$ or \(-\) we move left and
+goto 9.
+
+\item If the current symbol is \(*\) then we print \(-\) and goto 9. If we see \(-\) we move left and goto 10.
+
+\item If the current symbol is \(*, a\) then we move left and goto 10. If we see \(+\) we move right and goto
+7 to do another iteration.
+\end{enumerate}
+
+
+\section{Problem Four}
+\label{sec:orgdacb3cd}
+We can write the control tuples for the two-tape turing machine in the form: \((q_{\text{from}} , s_1, s_2, a_1, a_2, q_{\text{to}})\) 
+where s\textsubscript{n} is the expected symbol on tape \(n\), \(a_n\) is the action (R / L / new symbol) to perform on tape \(n\), \(q_{\text{from}}\)
+is the current state, and \(q_{\text{to}}\) is the next state.
+
+At a high level we can translate these control tuples to a single tape by separating the single tape into two sections; the
+first section simulates the first tape, and the other the second tape. These can be split by a single symbol \texttt{+} not in the alphabet (with the
+first cell also being \texttt{+}, representing the beginning of the input on the first tape). Additionally, the position of the tape
+head of the turing machine being simulated in its section can be delimited by some symbol not in the input alphabet in each section; call this
+symbol \texttt{*}.
+
+Thus, to build the initial tape we can construct the tape \texttt{+ * <input on tape 1> + * <input on tape 2>} (the head being at the beginning).
+Then, for each tuple in the two-tape turing machine \((q_{\text{from}} , s_1, s_2, a_1, a_2, q_{\text{to}})\) we construct a set of new states that will:
+
+\begin{enumerate}
+\item Search until we find \texttt{*} (we're at the head of the first "tape"), at which we go right one, and if we read s\textsubscript{1} goto 2.
+\item Search until we find \texttt{*} (we're at the head of the second "tape"), at which we go right one, and if we read s\textsubscript{2} goto 3.
+\item We perform a\textsubscript{2}.
+\begin{itemize}
+\item If \(s_2\) is the \texttt{+} symbol, we perform a new set of states to analyze the next symbol after; if it's non-\texttt{+} we shift all symbols proceeding
+to the right (this is a catch for 4 in the case we need to overwrite the \texttt{+} cell delimiting the two sections) and print a blank symbol. Then continue.
+\item If a\textsubscript{2} is "R" then we go left one (to the \texttt{*}), write s\textsubscript{2}, and go right one.
+\item If a\textsubscript{2} is "L" then we go back 2 (to the symbol preceding \texttt{*}) and from a new set of states constructed from all symbols in the alphabet go right and copy that symbol.
+Then we go back one and print "*".
+\item Else, we print a\textsubscript{2}.
+\item Finally, go left and goto 4.
+\end{itemize}
+\item Move left until we find \texttt{*} (we're now at the head of the first "tape") again and perform the same algorithm as 3 but with \(s_2 \rightarrow s_1 , a_2 \rightarrow a_1\). Then goto 5.
+\item Move left until we find the \texttt{+} symbol (we're at the head of the first tape) and move to the state corresponding to 1 with q\textsubscript{\text{to}}.
+\end{enumerate}
+
+\section{Problem Five}
+\label{sec:orgab00621}
+We can write the control quadruples for the 3D turing machine in the form: \((q_{\text{from}}, s, a, q_{\text{to}})\)
+where \(s\) is the expected symbol and \(a\) is the movement action \(\{ +x, -x, +y, -y, +z, -z \}\) or a symbol to print;
+where each movement action is a single step on the specified axis by either positive or negative one.
+
+At a high level we will apply our strategy in Problem 4 of delimination to construct several rows of tape into a
+"matrix" and then scale those into several matrices to produce a 3-dimensional tape; as one could emulate with
+\texttt{(make-array (list z y x))}.
+
+Then if we construct a one dimensional tape such that each "row" is a "tape" in the z axis then we "paste" the input
+into a one dimensional tape in the form \texttt{- = + * \_ <...[(0, 0, 0), (0, 0, 1)...]>} with the first five unique symbols not in the alphabet;
+the \texttt{-} indicating a new "matrix" in the z-y plane, and each \texttt{+} symbol a new row in the z direction. But now, we need to keep track of
+where we are in the \(z\) and \(y\) planes for every \(x\). To do so we can also create another three new symbols not in the
+alphabet; say \texttt{*} to stick with Problem 4 for the \(z\) plane, \texttt{=} for the \(y\) plane, and \texttt{\_} for the actual placement of the
+current head of the machine.
+
+Now, for each control tuple of the 3D turing machine we can construct a new set of states that will, at a high level:
+
+\begin{enumerate}
+\item Search until we find \texttt{\_} (we're at the head of the tape), at which we go right one, and if we read \(s\) goto 2.
+\item If \(a\) is \(\pm z\) then we move right or left.
+\begin{itemize}
+\item If this symbol is \texttt{+} we must then traverse to the very beginning of the tape and "increase the size" of every single \(z\) since the
+tape has the potential to now go in the \(x\) or \(y\) axes; we do this by searching for the first \texttt{+}, move right, shift the entire tape
+right one and print a blank symbol (to add an extra cell at the beginning), then continue searching for \texttt{+} and for each: shift the entire tape right one,
+move left, print a blank symbol, move right two, shift everything to the right one, move left, and print a blank symbol (adding a blank cell before and after
+each \texttt{+}).
+\item Then we go back to the beginning of the tape and continue moving right until we see \texttt{\_}.
+\end{itemize}
+\item If \(a\) is \(\pm y\) or \(\pm x\) then move left or right until the first instance of either \texttt{=} or \texttt{-} respectively and perform a similar kind of algorithm to copy
+the rows or matrices with blank \(z\) rows of the same size, adding rows / matrices if necessary should we hit the beginning or end of the tape (for \(x\)) or
+a new "matrix" (\texttt{-} for \(y\))..
+\end{enumerate}
+\end{document}
\ No newline at end of file
-- 
cgit v1.3

