\documentclass{article}
\input{6045preamble}


\begin{document}
\homework{3}{Prof. Ron Rivest}{Due: 6 March 2002}{}

\begin{problem}
  Problem 1.23, parts b and c.
\end{problem}

\begin{problem}
  Problem 1.25
\end{problem}

\begin{problem}
  Problem 1.32, part a
\end{problem}

\begin{problem}
  Suppose we allow a FA to move its head left or right after each
  symbol is scanned.  Formally, the transition function now will have
  the form:
  $$\delta: Q \times \Sigma \rightarrow Q \times \set{L, R}$$
  where $L$ and $R$ denote "left" and "right" respectively.
 
  The machine begins computation with the read head on the leftmost
  input symbol as usual.  At each step, the current state and the
  current symbol being scanned determine the next state and also
  whether the read head moves left or right.  The machine "halts" if
  the read head moves to the left of the first symbol or to the right
  of the last symbol.  It accepts the string if and only if the state
  entered during such a final move is an accepting state.  Note that
  the machine may loop forever; in this case it does not accept the
  input.
 
  Argue that such "left-right FA" (or LRFA) are no more powerful than
  ordinary FA.  That is, argue that LRFA accept only regular
  languages.
 
  (Hint: for each prefix of the input, determine inductively what
  happens if the machine moves left onto the last symbol of that
  prefix. Does it accept, loop, reject, or exit the prefix again
  moving to the right in some state?  Use this approach to construct a
  DFA that recognizes the same language.)
\end{problem}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
