CSC362 2004S, Class 9: From Regular Expression to DFA (1)

Admin
* Excused: Arjun
* Late: Piper, Angela, Choed
* Project, Phase 1 due NOW.
  * Please submit your project via email as a gzip'd tarball or as a bunch of attached files or any reasonable variant
* We have hired a new Mathematician (Keri Kornelson (sp?))
* Talks at 2:15 and 4:30.  (Finally, you can leave out the back :-)
* New homework: Written Homework 1
* Fun questions
  * Regular expression for <em>ab ("not ba") ba</em>?
    * (([bcd]*[cd]+)?[acd]*)*b*
      * Does this include all the strings that it should?
      * Does it include any that it shouldn't?
    * How can you be *sure* that this is correct?
      * Convert to optimal DFA and compare to known correct optimal DFA
      * Prove that there are no cases for which he is incorrect:
        * induce on the number of time we apply each * or +
        * induce on the length of the strings produced
      * Proof by contradiction
      * Sometimes the scientific method suffices
  * When did you need extra lookahead for the tokenizer?
    * Suppose you see a digit (e.g., 3).  If you peek at ...
      * A digit: Consume and append
      * A dot: Consume and append and EXPECT a digit
      * An e: It's some complicated exponentional form: Consume and continue
      * Almost anything else: Do not consume; we've finished the token
    * However, dots are problematic
      3..4
      * Need some variant of "extra buffer"

Overview:
* Review
* Limitations
* How to go from regexp to DFA
* From regexp to NFA

/Review/
* Three formal mechanisms for describing simple languages
  * Regular expressions
  * DFA
  * NFA
* Regular expressions are nondeterministic
  Consider ab*b
  We're reading input.  We see an a.  We see a b.  We see another b.  We don't make the decision until we run out of string or decide.
  a(b*b|b*c)
* Why are regular expressions preferable?
  * Concise
  * Somewhat readable
* Why are DFA preferable?
  * Easier for some problems
  * Directly implementable

/Going from RE to DFA/
* From RE to NFA
* From NFA to DFA
* From DFA to optimal DFA

/From RE to NFA/

Recursive translation:
* Translate the parts
* Combine 'em together
* At every stage, we will have an NFA with exactly one start state and exactly one final state

/From NFA to DFA/

* Try to simulate 'every possible path' through the NFA simultaneously
* States in DFA are sets of states in NFA

How many states can you have in the DFA if the NFA has four states