\documentclass{article}

\usepackage{hevea}

\oddsidemargin 0cm
\textwidth 17cm

\begin{document}


\title{CS 3100 -- Models of Computation -- Fall 2010}
\date{August 26, 2010}

\maketitle

\begin{center}
{\bf Notes 2, Handed out: August 26, 2010 during Lecture 2}
\end{center}

\begin{LARGE}


\begin{itemize}
\item Review Ch1Slides.pdf

\item Do you follow these?

  \begin{itemize}
  \item Tape, 'tape head', accepting state, rejecting state
  \item State
  \item Transition
  \item Alphabet
    \begin{itemize}
    \item What is the alphabet for Morse Code?
    \item How do you recognize ``SOS''
    \item Recall S = {\tt ...} O = {\tt ---} and of course E = {\tt .}
    \item So how do you tell apart from S and three Es?
    \item So what is really the alphabet?!
    \end{itemize}
  \end{itemize}
\item Writing practice: Write these mathematically
  \begin{itemize}
  \item Empty string
  \item Empty set
  \item Set containining empty string
  \item Set containining empty set
  \item Set containining an empty string and an empty set (now, why
    would you do that?!)
  \item String containing an empty set (Groan! Can you do this?)
  \item Union of set $\{a\}$ and itself
  \item The result of inserting $a$ and $b$ into $\{a\}$
  \end{itemize}
\item So can you model a tic-tac-toe game as an FA (a DFA)?

  \begin{itemize}
  \item Symbols
  \item Alphabet
  \item States 
  \item Transitions
  \item Transition table
  \item Accept states
  \end{itemize}

\item Repeat above exercise for Chess and then your favorite card game

\item Discuss Homework 1

\item Finish-up on the problem

\[ L_{any3hastwo1s} = \{ all\; strings\; over\; \{0,1\}
  \;  \mid  \; block\_condition \} \]

where

\( block\_condition = \)
  every  block  of  three  consecutive  symbols  has  
  at  least  two  1s

\item Approaches to DFA construction

  \begin{itemize}
  \item Premature optimization is bad
  \item Later you'll be using tools to build and optimize (minimize)
  \item Later you'll be using NFA to arrive at a DFA (``FA'') faster
  \item Some DFA WILL be exponential no matter what!
  \item That said, some tricks do work ofte
  \end{itemize}

\end{itemize}

TAKE A 5-MIN BREAK AT 11:25AM

\begin{itemize}
\item Got terrible automaton without optimization
\item Used minimization tool to get better machine
\item Then said ``aha, look back is bad'' ; keep state = ``seen so far''
\item That worked well!
\item Need something better!
  \begin{itemize}
  \item Consider ``Nth last symbol must be a 0'' $\Rightarrow$ FA has size $2^N$
  \item Reverse of this guy is great and small!
  \item ORDER IN WHICH YOU FEED INFO TO A DFA MAKES ALL THE DIFFERENCE!!!!!
  \item Error-correcting DFA
  \item Error-free case for 01001
  \item All one-bit errors over 01001 $\Rightarrow$ Groan! DFA is UGLY
  \item NFA will make BOTH THESE problems simpler than baby-food
  \item regular expressions -- your door-way to tell a computer what
    NFA you want !!
  \end{itemize}

\item How I used regular expressions to process your email using {\tt sed}

\item History of Alan Turing
  \ahrefurl{http://www.turing.org.uk/turing/}

\item DFA for predicting the onset of Epileptic seizures!
  See paper 
\ahrefurl{DFA-to-predict-epileptic-seizures.pdf} in class dir.


\end{itemize}

USING SED

See contents of 

\ahrefurl{SED-USAGE.txt} and \ahrefurl{unids.txt}

\end{LARGE}

\end{document}
