\documentclass{article}
\input{6045preamble}


\begin{document}
\handout{3}{Prof. Ron Rivest}{}{}{Handout 3: Optional problems}

\textbf{These are the problems we would have handed out for homework this
week, had we assigned homework. All of these problems are optional.}

\begin{problem}
  Problem 1.16 (page 86) parts $a$ and $b$
\end{problem}

\begin{problem}
  For the following regular expressions, produce an NFA that recognizes
  the same language:
  \begin{enumerate}
  \item The expression of problem 1.15, part $a$
  \item The expression of problem 1.15, part $b$
  \item The expression of problem 1.15, part $e$
  \end{enumerate}
\end{problem}

\begin{problem}
  Consider the following regular expression operations from the unix
  \texttt{grep} command. For each, prove that regular expressions as
  defined in class, with the new operation, still define regular
  languages:
  \begin{enumerate}
  \item \texttt{?}: If $R$ is a regular expression, then $R\mathtt{?}$
    is zero or one instances of $R$
  \item \texttt{(n,m)}: If $R$ is a regular expression, then
    $R\mathtt{(n,m)}$ is between $n$ and $m$ (inclusive) instances of
    $R$,
  \item \texttt{\{\}}: If $R$ is a regular expression, then
    $\mathtt{\{}R\mathtt{\}}$ is a string containing a contiguous
    substring that matches $R$. For example, \texttt{\{ac\}} contains
    \texttt{bbbacb} but not \texttt{bbabbcbb}. (Note: this is not from
    \texttt{grep}, since this is how \texttt{grep} usually regards
    regular expressions.)
  \end{enumerate}
\end{problem}

\begin{problem}
  Consider the informal definition of a \emph{finite state transducer}
  from Problem 1.19 (page 87). Formally, a finite state transducer is
  a five-tuple
  $$(Q, \Sigma, \Gamma, \delta, q_0)$$
  where
  \begin{itemize}
  \item $Q$ is a finite set of states,
  \item $\Sigma$ is a finite set, called the \emph{input alphabet},
  \item $\Gamma$ is a finite set, called the \emph{output alphabet},
  \item $\delta: Q \times \Sigma \rightarrow Q \times \Gamma$ is a
    function from states and the input alphabet to states and the
    output alphabet. Informally, this function takes the current state
    and the next character of the input, and gives you the next state
    and the next character of the output.
  \item $q_0 \in Q$ is the start state.
  \end{itemize}
  Note that there is no concept of ``accepting'' states. Finite state
  transducers map input strings to output strings. For this problem,
  however, we will make one change. In particular, we will allow
  transitions to produce no output. That is, the transition function
  is now
  $$\delta: Q \times \Sigma \rightarrow Q \times \left( \Gamma \cup
    \set{\epsilon} \right)$$
  So, let $T$ be a finite state transducer.
  Let $L(T)$ be the set of strings that can be produced by $T$. That
  is, run $T$ on all possible input and let $L(T)$ be the outputs it
  could produce. Prove that for any finite state transducer $T$,
  $L(T)$ is regular.
\end{problem}

\end{document}

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