\documentclass[12pt]{article}

\usepackage{tikz}
\usepackage{amsmath}
\usetikzlibrary{automata,positioning,arrows}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\N}{{\sf N}}
\newcommand{\goes}{\rightarrow}
\newcommand{\st}{\mathrel{:}}
\newcommand{\nth}{n^{th}}
\newcommand{\HALTONZ}{{\rm HALTON0 }}
\newcommand{\HALTONZns}{{\rm HALTON0}}

\newcommand{\es}{\emptyset}

\begin{document}

\newif{\ifshowsoln}
\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\centerline{\bf Homework 10 DUE May 11 at 11:00 AM REALLY DUE}

\centerline{\bf THIS HW IS THREE PAGES LONG!!!!!!!!!!!!!!!!!!!!}

\centerline{\bf GOTO THE NEXT PAGE}

\begin{enumerate}

\item
(30 points)
Write an algorithm that will, given a DFA, determines if there is some string
that is accepted by it. Do the algorithm from scratch.
For example, do not say something like {\it view the DFA as a graph and use Kruskal's Algorithm to
find a spanning tree}.

\centerline{\bf GOTO NEXT PAGE}

\newpage

\item
(30 points---5 points each)
In this problem we use WS1S notation.
(Make sure to label states A for accept, R for Reject, S for Stupid.)


\begin{enumerate}
\item
Draw a DFA for

$$\{ (x,X) \st x+1\in X \}.$$

\item

Draw a DFA for

$$\{ (x,X) \st x+1\notin X \}.$$

\item
Draw a DFA for

$$\{ (x,X) \st x+100\in X \}.$$

(You may use DOT DOT DOT notation.)

\item
Draw a DFA for

$$\{ X \st X \hbox{ has exactly 3 elements} \}.$$

\item
Draw a DFA for

$$\{ X \st X \hbox{ does NOT have exactly 3 elements} \}.$$

\item
Draw a DFA for

$$\{ X \st X \hbox{ has exactly 100 elements} \}.$$

(You may use DOT DOT DOT notation.)
\end{enumerate}


\centerline{\bf GOTO NEXT PAGE}

\newpage


\item
(40 points)
Let $M_1,M_2,\ldots,$ be a list of Turing Machines.

\begin{enumerate} %ENUM
\item
(20 points)
Let $TOT$ be the set of all Turing Machines that halt on ALL inputs.

Find a computable set $B$ of ordered triples such that:

$$TOT=\{ e \st (\forall x)(\exists y)[(e,x,y)\in B]\}$$

(This means that $TOT$ is in $\Pi_2$.)

\item
(20 points)

Let $HALT100$ be the set of all Turing Machines that halt on at least 100 inputs.

Find a computable set $B$ of ordered pairs such that:

$$HALT100=\{ e \st (\exists x)[(e,x)\in B]\}$$

(HINT: $x$ itself will code many numbers. You need to say how you do that coding.)

\end{enumerate} %ENUM


\end{enumerate} %ENUM

\end{document} %ENUM