From 6bf4b90c90f15f4ab60833bddf5b5756d1a6b1f6 Mon Sep 17 00:00:00 2001 From: Elizabeth Alexander Hunt 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{+ * + * } (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