Created
February 7, 2020 00:27
-
-
Save meanmachin3/410497c65f639b2487b8228c0de66ea8 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
% Structured General Purpose Assignment | |
% LaTeX Template | |
% | |
% This template has been downloaded from: | |
% http://www.latextemplates.com | |
% | |
% Original author: | |
% Ted Pavlic (http://www.tedpavlic.com) | |
% Modified by: | |
% Joe Del Rocco (https://joe.delrocco.org) | |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
%---------------------------------------------------------------------------------------- | |
% PACKAGES AND CONFIGURATION | |
%---------------------------------------------------------------------------------------- | |
\documentclass[fleqn]{article} | |
\usepackage{geometry} | |
\usepackage{fancyhdr} % For custom headers | |
\usepackage{lastpage} % To determine the last page for the footer | |
\usepackage{extramarks} % For headers and footers | |
\usepackage[most]{tcolorbox} % For problem answer sections | |
\usepackage{graphicx} % For inserting images | |
\usepackage{xcolor} % For link coloring | |
\usepackage[hidelinks]{hyperref} % For URL links (no box or color name) | |
% Margins | |
\geometry{ | |
a4paper, | |
tmargin=1in, | |
bmargin=1in, | |
lmargin=1in, | |
rmargin=1in, | |
textwidth=6.5in, | |
textheight=9.0in, | |
headsep=0.25in | |
} | |
% Header and footer | |
\pagestyle{fancy} | |
\lhead{\myName} % Top left header | |
\chead{\myCourse: \myAssignment} % Top center header | |
\rhead{\firstxmark} % Top right header | |
\lfoot{\lastxmark} % Bottom left footer | |
\cfoot{} % Bottom center footer | |
\rfoot{Page\ \thepage\ of\ \pageref{LastPage}} % Bottom right footer | |
\renewcommand\headrulewidth{0.4pt} % Size of the header rule | |
\renewcommand\footrulewidth{0.4pt} % Size of the footer rule | |
% Other configurations | |
\setlength\parindent{0pt} % Removes all indentation from paragraphs | |
\setlength\parskip{1pt} % Ensures paragraphs are still recognizable as such | |
\setcounter{secnumdepth}{0} % Removes default section numbers | |
\setcounter{tocdepth}{3} % Sets depth of table of contents | |
\linespread{1.1} | |
% Template values | |
\newcommand{\myLogo}{starfleet.jpg} | |
\newcommand{\myName}{Manish Yadav} | |
\newcommand{\myJobTitle}{3836-6483} | |
\newcommand{\myCompany}{Starfleet Academy} | |
\newcommand{\myLocation}{1701 Lincoln Blvd, San Francisco, CA} | |
\newcommand{\myURL}{www.starfleet.edu} | |
\newcommand{\myEmail}{m.yadav@ufl.edu} | |
\newcommand{\myCourse}{EEL\ 6825} | |
\newcommand{\mySection}{Spring 2020} | |
\newcommand{\myTeacher}{Dr. Dapeng Wu} | |
\newcommand{\myAssignment}{Homework 1} | |
\newcommand{\myDueDate}{Friday,\ February\ 6,\ 2020} | |
%---------------------------------------------------------------------------------------- | |
% DOCUMENT STRUCTURE (MACROS & ENVIRONMENTS) | |
%---------------------------------------------------------------------------------------- | |
% Colored links macro | |
\newcommand{\hrefcol}[3] {\href{#1}{\textcolor{#3}{#2}}} | |
% Creates a counter to keep track of the number of problems | |
\newcounter{homeworkProblemCounter} | |
% Macro for custom title page signature header | |
\newsavebox{\myTitleSignature} | |
\sbox{\myTitleSignature}{% | |
\begin{tabular*}{\textwidth}{@{}l@{}|@{\extracolsep{0.125in}}l@{}}% | |
\parbox[c][]{2.5in}{{\textbf{\myName} \par} | |
{\small \myJobTitle \par} | |
{\small \hrefcol{mailto:\myEmail}{\myEmail}{blue}} \par} | |
\end{tabular*}} | |
% Header and footer for when a page split occurs within a problem environment | |
\newcommand{\enterProblemHeader}[1]{% | |
\nobreak\extramarks{#1}{#1 continued on next page\ldots}\nobreak% | |
\nobreak\extramarks{#1 (continued)}{#1 continued on next page\ldots}\nobreak% | |
} | |
% Header and footer for when a page split occurs between problem environments | |
\newcommand{\exitProblemHeader}[1]{% | |
\nobreak\extramarks{#1 (continued)}{#1 continued on next page\ldots}\nobreak% | |
\nobreak\extramarks{#1}{}\nobreak% | |
} | |
\newcommand{\homeworkProblemName}{} % Argument = name of problem; default = "Problem #" | |
\newenvironment{homeworkProblem}[1][Problem \arabic{homeworkProblemCounter}]{% | |
\stepcounter{homeworkProblemCounter}% % Increase counter for number of problems | |
\renewcommand{\homeworkProblemName}{#1}% % Assign \homeworkProblemName the argument | |
\section{\homeworkProblemName}% % Make a section in the document with the custom problem count | |
\enterProblemHeader{\homeworkProblemName}% % Header and footer within environment | |
}{% | |
\exitProblemHeader{\homeworkProblemName}% % Header and footer after environment | |
} | |
\newcommand{\problemAnswer}[1]{ % Defines the problem answer command with the content as the only argument | |
\begin{tcolorbox}[breakable,enhanced,colback=gray!5!white,title=Answer]% | |
#1 | |
\end{tcolorbox}% | |
% Alternative - Makes the box around the problem answer and puts the content inside | |
%\noindent\framebox[\columnwidth][c]{\begin{minipage}{0.98\columnwidth}#1\end{minipage}} | |
} | |
\newcommand{\homeworkSectionName}{} | |
\newenvironment{homeworkSection}[1]{% % For sections w/in problems; Argument = name of section (no default) | |
\renewcommand{\homeworkSectionName}{#1}% % Assign \homeworkSectionName the argument | |
\subsection{\homeworkSectionName}% % Make a subsection with the name of the subsection | |
\enterProblemHeader{\homeworkProblemName\ [\homeworkSectionName]}% % Header and footer within environment | |
}{% | |
\enterProblemHeader{\homeworkProblemName}% % Header and footer after environment | |
} | |
%---------------------------------------------------------------------------------------- | |
% TITLE PAGE | |
%---------------------------------------------------------------------------------------- | |
\begin{document} | |
% Blank out the traditional title page | |
\title{\vspace{-1in}} % no title name | |
\author{} % no author name | |
\date{} % no date listed | |
\maketitle % makes this a title page | |
% Use custom title macro instead | |
\usebox{\myTitleSignature} | |
\vspace{1in} % spacing below title header | |
% Assignment title | |
{\centering \huge \myAssignment \par} | |
{\centering \noindent\rule{4in}{0.1pt} \par} | |
\vspace{0.05in} | |
{\centering \myCourse~: \mySection~: \myTeacher \par} | |
{\centering Due \myDueDate \par} | |
%{\centering Prepared w/ \LaTeX \par} | |
\vspace{1in} | |
% Table of Contents | |
\tableofcontents | |
\newpage | |
%---------------------------------------------------------------------------------------- | |
% PROBLEM 1 | |
%---------------------------------------------------------------------------------------- | |
%\begin{homeworkProblem}[Exercise \#\arabic{homeworkProblemCounter}] % Use for custom section title | |
\begin{homeworkProblem} | |
Define $ND$ or $NotDominating = \{~f \mid \text{for some } x, f(x) < x~\}$. | |
%----------------------------------------------- | |
%\begin{homeworkSection}{\homeworkProblemName:~(a)} % Use for repeating problem name | |
\begin{homeworkSection}{(a)} | |
Show some minimal quantification of some known primitive recursive predicate that provides an upper bound for the complexity of $ND$.\par | |
\problemAnswer{ | |
We can quantify with primitive recursive predicates like so:\par | |
$\exists\langle x,t\rangle[STP(f,x,t) ~\&\&~ VALUE(f,x,t) < x]$\par | |
\vspace{5pt} | |
Because of the quantifier $\exists$, the problem is no harder than a problem in the RE (or Recursively Enumerable) problem class. | |
} | |
\end{homeworkSection} | |
%----------------------------------------------- | |
\begin{homeworkSection}{(b)} | |
Show that $K \leq_m ND$, where $K = \{~ f \mid f(f) \text{ converges} ~\} = \{~ f \mid \varphi_f(f)\downarrow ~\}$.\par | |
\problemAnswer{ | |
Let $f$ be an arbitrary index of function.\par | |
Define $g_f(z) = \varphi_f(f) - \varphi_f(f) + z$\par | |
$f \in K \implies \forall z ~g_f(z) = z \implies g_f(z)\downarrow \implies g_f \in ND$\par | |
$f \notin K \implies \forall z ~g_f(z)\uparrow \implies g_f \notin ND$\par | |
Thus, $f \in K \iff g_f \in ND$\par | |
And so, $K \leq_m ND$ | |
} | |
\end{homeworkSection} | |
\end{homeworkProblem} | |
%---------------------------------------------------------------------------------------- | |
% PROBLEM 2 | |
%---------------------------------------------------------------------------------------- | |
\begin{homeworkProblem} | |
Consider the languages: \par | |
\hspace{0.5in} $ L = \{~ a^mb^nc^t \mid t=min(m,n) ~\} $ \par | |
%----------------------------------------------- | |
\begin{homeworkSection}{(a)} | |
Use the \textbf{Myhill-Nerode Theorem} to show that $L$ \textbf{is not} a \underline{Regular Language}. | |
\vspace{10pt} | |
\problemAnswer{ | |
\textbf{\small Proof Idea} \par | |
We need to find the equivalence classes of the language $L$, and show that you would need an infinite number of states to implement them. As an FSA cannot have infinite states, $L$ cannot be regular. \par | |
\vspace{3pt} | |
\textbf{\small Proof} \par | |
$a^ib^jc^j \notin L$, where $j > i$ \par | |
$a^ib^jc^j \in L$, where $i \geq j$ \par | |
Because there are no limits on $i$, there are a countably infinite number of these classes. Because a FSA must have a finite number of states, you cannot construct one to recognize $L$. Therefore $L$ is not a Regular Language. | |
} | |
\end{homeworkSection} | |
%----------------------------------------------- | |
\begin{homeworkSection}{(b)} | |
Use the \textbf{Pumping Lemma for CFLs} to show that $L$ \textbf{is not} a \underline{Context Free Language}. | |
\vspace{10pt} | |
\problemAnswer{ | |
This is a proof by contradiction. \par | |
Assume $L$ is a Context Free Language. \par | |
And the \underline{Pumping Lemma for CFL} states that any string $s \in L = uvxyz$, where: \par | |
1. $\forall i \geq 0,~ uv^ixy^iz \in L$ \par | |
2. $\mid vy \mid > 0$ \par | |
3. $\mid vxy \mid \leq p$ \par | |
There are 2 cases to consider: (1) $t = n$, and (2) $t = m$. \par | |
\vspace{3pt} | |
\textbf{\small Case 1} \par | |
Choose string $s = a^mb^nc^t$, where $t=n$. \par | |
Then there are more $a$ than $b$, for example $a^3b^2c^2=aaabbcc$. \par | |
Let $i$ be $0$. \par | |
If $vxy$ contains both $a$ and $c$, then with $i=0$, the number of $c$ are not equal to either $a$ or $b$. \par | |
(for example $a^3b^2c^2=aaabbcc=aaa^0bbc^0c=aabbc~\notin~L$) \par | |
Thus we have a contradiction. \par | |
\vspace{3pt} | |
\textbf{\small Case 2} \par | |
Choose string $s = a^mb^nc^t$, where $t=m$. \par | |
Then there are less $a$ than $b$, for example $a^2b^3c^2=aabbbcc$. \par | |
Let $i$ be $0$. \par | |
If $vxy$ contains $a$ and $b$ but no $c$, then with $i=0$, $t \ne m$ and the number of $c \ne \min(m,n)$. \par | |
(for example $a^2b^3c^2=aabbbcc=aa^0bbb^0cc=abbcc~\notin~L$) \par | |
Thus we have a contradiction. \par | |
\vspace{3pt} | |
Therefore $L$ cannot be a Context Free Language. | |
} | |
\end{homeworkSection} | |
\end{homeworkProblem} | |
%---------------------------------------------------------------------------------------- | |
% PROBLEM 3 | |
%---------------------------------------------------------------------------------------- | |
\begin{homeworkProblem} | |
Explain what a \underline{tachyon} is.\par | |
\vspace{10pt} | |
\problemAnswer{ | |
A tachyon is a subatomic particle that naturally exists at faster-than-light velocities. They can often be associated with time travel or produced as a byproduct of temporal distortions. Tachyons can exist both naturally, as in the tachyon eddies in the Bajoran system, and as the byproducts of certain technologies, such as cloaking devices and transporters. The detection of tachyons may lead to clues about recent temporal or spactial anomalous. | |
} | |
\end{homeworkProblem} | |
\end{document} | |
%---------------------------------------------------------------------------------------- | |
% DONE | |
%---------------------------------------------------------------------------------------- |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment