\documentclass[10pt]{article}

\usepackage{hevea}

\oddsidemargin 0cm
\textwidth 17cm

\begin{document}

\thispagestyle{empty}

\begin{center}
{\bf CS 3100 -- Models of Computation -- Fall 2010}\\
{\bf Notes 5, Handed out: September 7, 2010 during Lecture 5}\\
{\bf Will definitely last through Thursday, September 9, 2010, Lecture 6}
\end{center}



\begin{enumerate}
\item[]{\bf Class Lecture:}
\item 
  On exponentially succinct notations.
\item
  Importance of patterns.  We will need more complex pattern classifiers for
  non-regular patterns.
  \begin{enumerate}
  \item Regular patterns $(0^* 1^*)$, $(0^* 1^*)^*$, $(a^* (b b)^* cc )^*$ 
  \item Non-regular patterns (have no RE that can express them)
 $\{a^{n^2}\;\mid\; n\ge 0\}$,
 $\{a^n b^n \;\mid\; n\ge 0\}$,
 $\{(^n )^n \;\mid\; n\ge 0\}$,
 $\{a^n b^m c^n d^m \;\mid\; m,n\ge 0\}$
  \end{enumerate}

\item {\bf NOTE:}
 $\{a^{2n}\;\mid\; n\ge 0\}$ is regular, because this is
 nothing but even length $a$s.

\item 
  Review RE to NFA steps.
  Draw an NFA for $ab+ac$ with and without $\varepsilon$.
  Draw the NFA tables in each case.

\item
  Obtain its equivalent DFA in each case.

\item
  Convert this NFA into an equivalent DFA:
\begin{verbatim}
D and F are final states:

    /--a--> B --b--> D --c--> A
-> A
   \--a--> C  --b--> E --c--> F

\end{verbatim}


\item
  Convert this NFA into an equivalent DFA:
\begin{verbatim}
D and F are final states. e means epsilon

    /--a--> B -- e --> D -- e --> A
-> A
    \-- e --> C  --b--> E --c--> F

\end{verbatim}

\item
  Draw an NFA for $a^*$.
  Obtain its equivalent DFA without first simplifying the NFA.

\item 
  Homework 2 discussions.

\item
  Write an RE for the set of all strings over $\{0,1\}$ such
  that every even position is a $0$.

\item 
  What is the complement of this language?

\item
  Write an RE for the complement of this language.

\item 
  Convert the RE $( (a+b)^* a a^* ) ^*$ into an NFA.

\item
  Simplify this NFA.

\item
  Convert this NFA into a DFA.

\item
  Simplify this DFA.

\item
  Convert this DFA into an RE.


\item[]{\bf TA Assisted Part:}

\item
  Convert this NFA into an equivalent DFA:
\begin{verbatim}
A and F are final states:

    /--a--> B --b--> D --c--> A
-> A
   \--a--> C  --b--> E --c--> F

\end{verbatim}


\item
  Convert this NFA into an equivalent DFA:
\begin{verbatim}
A, D,  and F are final states. e means epsilon

    /--a--> B -- e --> D -- e --> A
-> A
    \-- e --> C  --b--> E --c--> F

\end{verbatim}

\item 
  Write an RE for the set of all odd-length strings over $\{0,1\}$.

\item 
  Call the language of the above RE $L$. What is the complement of this language?

\item
  Write an RE for the complement of this language.

\item
  Describe differences, if any, between $(a^* b)^*$ 
  and $(a^* b^*)^*$ 

\item
  Convert $a+(a^*b)^*$ to an NFA.

\item 
  Simplify this NFA.

\item 
  Convert this NFA to a DFA.

\item 
  Simplify this DFA.

\item
  Convert this DFA to an RE.
  

\end{enumerate}


\end{document}
