\documentclass[12pt]{cas-handout}
\usepackage{multicol}
\usepackage{paralist,boxedminipage}

\newtheorem{theorem}{Theorem}

\newcommand{\BAR}{\ |\ }
\anumber{8}
\title{Regular Languages}
\duedate{11am, Wednesday, November 14, 2012}

\begin{document}
\maketitle

\begin{itemize}
  \item Emails about this assignment should be directed to
   \helpalias.
 \item Your diagrams may be hand-drawn or computer-drawn via
   a program of your choice.  If you use special-purpose tools such
   as JAPE to draw your automata, do \emph{not} use it to solve the
   problems, e.g., converting between NFAs, DFAs, and regular expressions.
   (After all, you won't be able to use JAPE during the final exam!)
 \item
   All work submitted must be your own.
\end{itemize}

\hrule


\section{Regular Languages}

\begin{enumerate}
  \item Review Chapters 1--3 of Rich (\textit{Automata, Computability, and Complexity}),
    paying particular attention to
  all the
  examples (in the shaded boxes). Then do the same for Chapter 5 up
  through and including section 5.4.2.

  Come up with two questions related to the reading.
  These may refer to points where the book
  is confusing, or simply to some question or conjecture that
  occurs to you while doing the reading.

\item Turn the following NFAs into DFAs (DFSMs) using the subset
construction. It should be clear from your drawing of a DFA how the
subset construction was applied.

\begin{enumerate}
\item \

  \includegraphics{Pictures/nfa1}

\goodbreak

\item \

  \qquad \includegraphics{Pictures/nfa2}
\end{enumerate}
\bigskip


\item Do Exercise 2(a,c--e,j,o--r,t) on pages 151--152 of Rich.
\bigskip

\item
  For two languages $L$ and $M$, let the \emph{shuffle} of $L$ and $M$
  be the set
     \[
       \{\ w \BAR w = a_1b_1\cdots a_kb_k\mbox{,\ where\ }a_1\cdots a_k\in L \mbox{\ and\ }
          b_1\cdots b_k\in B\ \}
     \]
  Here $a_1\cdots a_k$ is
  a \emph{single} word in $A$, and the $a_i$'s are pieces of
  that word; any of the $a_i$'s might be the empty
  string. The same ideas hold for the $b_i$'s.

  So for example, strings in the shuffle of $\mathtt{a}^{+}$
  and $\mathtt{b}^{+}$ include \texttt{abab},
  \texttt{aabaabb}, \texttt{aabbaa}, \texttt{ba},
  \texttt{babbabbaaa}, and so on. The intuition is to take a single
  string from $A$ and a single string from $B$ and do the
  equivalent
  of one ``riffle shuffle'' of two piles of cards.)

  Prove clearly and convincingly that if $L$ and $M$ are regular
  then the shuffle of $L$ and $M$ is also regular.  (Hint: if $L$ and $M$
  are regular, then there are NFAs and DFAs that accept each. Show how
  these can be used to construct an automaton that can say whether
  the input is a valid combination of a string in $L$ and a string in $M$.)


\item A \emph{lexer} (also known as a \emph{tokenizer})
  is a program that takes a
  sequence of characters and splits it up into a sequence of words, or
  ``tokens.'' Compilers typically do this as a prepass before parsing
  programs. For example ``\texttt{if (count == 42) ++n;}''
  might divide into \  \texttt{if}\ , \ \texttt{(}\ , \
  \texttt{count}\ ,
  \ \texttt{==}\ , \ \texttt{42}\ , \ \texttt{)}\ , \ \texttt{++}\ ,
  \ \texttt{n}\ , and \ \texttt{;}\ .

Regular
  expressions are a convenient way to describe tokens (e.g., C integer
  constants) because they are unambiguous and compact.  Further, they
  are easy for a computer to understand: \emph{lexer
    generators} such as \texttt{lex} or \texttt{flex} can turn
  regular expressions into
  program code for dividing characters into tokens.

  In general, there may be many ways to divide the input up into
  tokens.  For example, we might see the
  input \texttt{ifoundit = 1} as starting with a single token
  \texttt{ifoundit} (a
  variable name) or as starting with the keyword \texttt{if}
  followed immediately
  by the variable \texttt{oundit}.  Most commonly, lexers are
  implemented to be \emph{greedy}\/: given a choice, they match
  the longest token.
  (Hence, \texttt{ifoundit} is preferred over
  \texttt{if} as the first token.)



  Lexers commonly skip over whitespace and comments.  A
  ``traditional'' comment in C starts with with the characters
  \texttt{/*} and runs until the next occurrence of \texttt{*/}.
  Comments do not nest; the string \texttt{/*~a~/*~b~*/~c~*/} consists of
  a C comment (\texttt{/*~a~/*~b~*/}) followed by non-comment (code) charaters
  (\texttt{c */}).

Your task is to construct a regular expression for these traditional C comments,
one suitable for use in a lexer generator.\footnote{Some regular
  expression implementations supply both ``greedy'' and ``nongreedy''
  matching operators, e.g., a non-greedy version of the star operator that
  matches as few times as possible. These makes this problem trivial;
  our goal here is to find a correct regular expression just using the
  ``classic''
  operators.}
\goodbreak

   \begin{enumerate}
    \item When I have given this problem in the past,
    people immediately suggest
   \begin{Verbatim}[commandchars=&\{\}]
    /* &ensuremath{&bigl(}. &ensuremath{&bigm|} \n &ensuremath{&bigr)&sp{*}}*/
    \end{Verbatim}
    Explain why this regular expression
    would not make a lexer skip comments correctly.  (Big hint: greed.)

    \item Once the problem with the previous expression is
    noted, most folks decide that comments should contain only
    characters that are not stars, plus stars that are not immediately
    followed by a slash. This leads to the following regular expression:
    \begin{Verbatim}[commandchars=&\{\}]
    /* &ensuremath{&bigl(} [^*] &ensuremath{&bigm|} *[^/] &ensuremath{&bigr)&sp{*}} */
    \end{Verbatim}
    Find a legal 5-character C comment that the regular expression
    fails to match, and a 7-character ill-formed (non--valid-comment) string that the
    regular expression erroneously matches.

  \item Draw a finite-state machine that accepts all and only valid
    traditional C comments.

  \item Provide a correct regular expression that matches all and only
    valid C traditional comments, by converting your state machine
    into a regular expression.  You may use either method from class,
    but show your work.

   Be sure it's completely clear where you're using \texttt{*} the
   character and when you're using $^*$ the regular expression
   notation.
   \end{enumerate}



\end{enumerate}

\end{document}
