\documentclass[12pt]{amsart}
\usepackage{amsmath} \usepackage{amsthm} \usepackage{amstext}
\usepackage{amsfonts} \usepackage{graphicx} \usepackage{latexsym}
\usepackage{epsfig}
% \input epsf
\def\p{\partial} \def\O{\Omega} \def\c{\cal} \def\a{\alpha}
\def\r{\rho} \def\e{\epsilon} \def\g{\gamma} \def\d{\delta}
\def\D{\Delta} \def\t{\theta} \def\T{\Theta} \def\N{\nabla}
\def\L{\Lambda} \def\l{\lambda} \def\m{\mu} \def\f{\frac}
\def\dis{\displaystyle} \def\s{\sigma}
\newcommand{\lx}{\left} \newcommand{\rx}{\right}
\setlength{\parindent}{0in} \setlength{\parskip}{\baselineskip}
\setlength{\textheight}{9.0in} \setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0.0in} \setlength{\evensidemargin}{0in}
\setlength{\oddsidemargin}{0in}

\begin{document} %(
\baselineskip 24pt

\title{Problem Set 10}
% YOUR NAME GOES HERE under Author
\author{Your Name}
\maketitle

\begin{enumerate} %(
\item Write all the 4 letter strings that are elements of the language
described by the regular expression: {\tt A*B*(AB)*}

% Answer below this line.


\item Consider a Finite State Automaton that has 3 states: 1, 2, and
3.  State 1 is the start state, and state 3 is the accepting state.
The state transitions are as follows:
\begin{center} %(
\begin{tabular}{ccc} %(
{\bf In state} & {\bf and reading} & {\bf goto state} \\
             1   &        {\tt A}      &       2      \\
             1   &        {\tt B}      &       3      \\
             2   &        {\tt A}      &       1      \\
             2   &        {\tt B}      &       3      \\
             3   &        {\tt A}      &       1      \\
             3   &        {\tt B}      &       3      \\
\end{tabular} %)
\end{center} %)

\begin{enumerate} %( 
\item Write a regular expression that has the same language as this
FSA.

% Answer below this line.


\item Write the transitions for a 2 state FSA that has the same
language as the 3 state FSA above.  Be sure to say which states are
accepting states, and which state is the start state.

% Answer below this line.

\end{enumerate} %)


\item Construct a Turing machine that takes in a string of {\tt
A}s and {\tt B}s (followed by empty tape), and writes a {\tt B} at the
right of the string (the halts) if there are an even number of {\tt
A}s, and writes an {\tt A} if the number of {\tt A}s in the
string is odd.  You can assume that the reader head is at the leftmost
character of the string.

% Answer below this line.


\item Count Vlad Urr gives Ossub Ull, the court Imp (not to be
confused with Ido Urr, the court Gog), the task of writing the function
{\tt boolean printsA(Program P)} that takes an arbitrary program {\tt
P}, and in finite time returns whether {\tt P} (when executed) prints
the letter {\tt A}.  Can you prove that Imp Ossub Ull's task is
impossible?

% Answer below this line.


\item BONUS: Upon being again countered, Count Urr orders that 
{\em Gog Ido Urr go sum}mon The High Programmer.  Upon arrival, The High
Programmer states ``This might not be as hard as {\em I think.  Therefore,
I am} inclined to say that Imp Ossub Ull's task is possible if the input
{\tt P} will never have more than 256 lines of code and never use more
than 24 bits of memory (including registers).''.  With these restrictions
on {\tt P}, can one construct {\tt printsA}?  If so, how would {\tt
printsA} work?  (An outline of the algorithm is sufficient.)  If not,
please explain why.

% Answer below this line.


\end{enumerate} %)
\end{document} %)