% This is a TeX file
% It is essentially a programming language for mathematics documents
% You can ignore this first portion of the file, as it is essentially a bunch of "include" statements.
\documentclass[10pt]{article}

\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{graphics}
\usepackage{fullpage}
\usepackage{fancyhdr}
\usepackage{hyperref}

\usepackage{algorithm,algorithmic}
\usepackage{multirow}

\setlength{\voffset}{-0.25in}
\setlength{\headsep}{0.25in}
\setlength{\parskip}{1em}
\setlength{\parindent}{0em}

% The following denotes a counter for the problems.
\newcounter{problem}
\newcommand{\problem}{\textbf{\refstepcounter{problem}Problem \theproblem.} }

% These are macro shortcuts! Helpful!
\def\vu{\mathbf{u}}
\def\vx{\mathbf{x}}
\def\vy{\mathbf{y}}
\def\vz{\mathbf{z}}
\def\vb{\mathbf{b}}
\def\vv{\mathbf{v}}
\def\vw{\mathbf{w}}

\renewcommand{\implies}{\rightarrow}
%\newcommand{\lnot}{\neg}
\renewcommand{\lor}{\vee}
\renewcommand{\land}{\wedge}
\newcommand{\xor}{\oplus}
\newcommand{\symmdiff}{\triangle}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\TRUE}{\mathbf{T}}
\newcommand{\FALSE}{\mathbf{F}}
\newcommand{\universe}{\mathcal{U}}


\def\N{\mathbb{N}}
\def\Q{\mathbb{Q}}
\def\C{\mathbb{C}}
\def\Z{\mathbb{Z}}
\def\R{\mathbb{R}}
\def\cP{\mathcal{P}}


\begin{document}
\pagestyle{fancyplain}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% NOW you can start typing your text that will appear in the PDF!!!

% Note that anything after a '%' is a comment!

% Anything immediately after a '\' is a command. 
% Some denote formatting, some are for special characters.
% The '$' symbol starts and ends "math mode". Use this only for mathematical statements
% In math mode, any sequence of letters is meant to be a list of variables, so use "\sin x" for the sine of x, which will look much different from "sin x"
\chead{COM S 330 --- Homework 08 --- INSERT NAME HERE}

\textit{Type your answers to the following questions and submit a PDF file to Blackboard. 
One page per problem.}


% Problems about State Machines! Monotonicity Principle!
\problem\ [10pts] Let $M = (S,T, s_0)$ be the state machine where $S = \N \times \N$ and the transitions in $T$ are given as
$(m,n) \to (m-1,n+1)$ if $m \geq 1$, and $(m,n) \to (m, n-1)$ if $n \geq 1$. 
Define a function $f : \N \times \N \to \N$ where $f$ is decreasing with respect to $M$ and use the Monotonicity Principle to prove that if the initial state is $(m,n)$, then the machine will halt in at most $f(m,n)$ transitions. (Bonus 1pt for defining $f(m,n)$ to be \emph{optimal}, predicting exactly the maximum number of steps from $(m,n)$ to a halting state.) [Hint: Draw the points $(m,n)$ in the plane and draw lines between points for possible transitions.]

% Problems about State Machines! 
% \clearpage
\problem\ [10pts] Let $\Sigma = \{ a^+, a^-, b^+, b^-\}$.
Let $M = (S,T,s_0)$ be the state machine where $S = \Sigma^*$ and the transitions available in $T$ from a string $x_1\dots x_n \in \Sigma^*$ are as follows:
\vspace{-1em}
\begin{itemize}
\item If there exists $i \in \{1,\dots,n-1\}$ such that $x_i = a^+$ and $x_{i+1} = a^-$, then $x_1\dots x_n \longrightarrow x_1\dots x_{i-1}x_{i+2}\dots x_n$.
\item If there exists $i \in \{1,\dots,n-1\}$ such that $x_i = a^-$ and $x_{i+1} = a^+$, then $x_1\dots x_n \longrightarrow x_1\dots x_{i-1}x_{i+2}\dots x_n$.
\item If there exists $i \in \{1,\dots,n-1\}$ such that $x_i = b^+$ and $x_{i+1} = b^-$, then $x_1\dots x_n \longrightarrow x_1\dots x_{i-1}x_{i+2}\dots x_n$.
\item If there exists $i \in \{1,\dots,n-1\}$ such that $x_i = b^-$ and $x_{i+1} = b^+$, then $x_1\dots x_n \longrightarrow x_1\dots x_{i-1}x_{i+2}\dots x_n$.
\end{itemize}
\textbf{a.} [5pts] Describe all of the possible state sequences when starting at the string $b^+a^+b^+b^-a^-b^+a^+b^-b^+$.

\textbf{b.} [5pts] For certain states in $\Sigma^*$, there may be more than one outgoing transition. Prove that for every string $\vx \in \Sigma^*$, there is a unique halting state reachable from $\vx$. [Hint: Use induction on the length of $\vx$, and consider the following strengthened statement: For every state $\vx$ with outgoing transitions $\vx \to \vy^{(i)}$ for $i \in \{1,\dots,k\}$, all states $\vy^{(1)},\dots,\vy^{(k)}$ halt in the same state, $\vz$.]


% Reversibility Principle!
% \clearpage
\problem\ [10pts] Let $M = (\Q, T, s_0)$ be a state machine on the rational numbers with transitions $\frac{p}{q} \to \frac{p}{q} + \frac{1}{pq} = \frac{p^2+1}{pq}$, when $p > 0$ and $q > 0$. 

\textbf{a.} [5pts] Let $P_d(\frac{p}{q})$ be the property ``$d \leq \frac{p}{q} < d+1$.''
Prove that when $d$ is an integer with $d \geq 2$, $P_d$ is a reversible invariant for the state machine $M$.
[Hint: If $P_d(\frac{p}{q})$ is true, then $p = dq + r$ where $r$ is an integer and $0 \leq r < q$.]

\textbf{b.} [5pts] Use part (a) and the Reversibility Principle to say that if $\frac{p}{q}$ is the initial state and $\frac{i}{j}$ is a reachable state, then $\lfloor \frac{p}{q}\rfloor = \lfloor \frac{i}{j}\rfloor$.
[You can get full points for this part if you assume (a), even if you have not proven (a) correctly.]

\textbf{c.} [Bonus 1pt] Find a fraction $\frac{p}{q}$ such that $P_1(\frac{p}{q})$ is true but $P_1(\frac{p^2+1}{pq})$ is false.

% Problems about Structural Induction!
% \clearpage
\problem\ [10pts] Define a set $S \subseteq \R$ recursively using the Recursive Step ``If $x \in S$, then $(x-1)(x+1) \in S$.'' Consider the following bases.

\textbf{a.} [3pts] Prove that if the basis step is ``$0 \in S$'' then $S = \{ 0, -1 \}$.

\textbf{b.} [3pts] Prove that if the basis step is ``$1 \in S$'' then $S = \{ 1, 0, -1 \}$.

\textbf{c.} [4pts] Prove that if the basis step is ``$2 \in S$'' then $S$ is an infinite set.


% Problems about Structural Induction!
% \clearpage
\problem\ [10pts] Define a set $S \subseteq \R$ recursively by (Basis Step) $\frac{1}{1} \in S$, and (Recursive Step) If $x \in S$, then $2x \in S$ and $\frac{x}{3} \in S$. Prove that $S = \{ \frac{2^i}{3^j} : i, j \in \N \}$.














\end{document} 