CSC362 2011F, Class 09: From Specification to Optimal DFA (2)
Overview:
* NFAs.
* Where we're going: From regular expression to code.
* From regular expressions to NFAs.
* Examples.
Admin:
* Don't forget that assignment 2 is due tonight.
* EC for Kington tomorrow
* EC for Robotics tomorrow
* EC for Bread and Puppets on Monday, Mac Field, 5-8 or 6-9. Read posters.
* Really massively puppeteristic awesome art performance
Questions on Assignment 2
* What punctuation? It's in the reading
SEMI
COLON
ELLIPSES
3..4
* Hard parts?
Getting strings right 'O''Toole'
Real numbers and ints
Identify everything
* Learning that you should write programs to automate repetitive tasks
DFAs and Regular Expressions
* Both describe sets of strings
* Both used to represent tokens
* RegExp: Declarative What it looks like
DFA: Imperative: Executable
Quick example
* Strings of a's and b's in which every a is immediately followed by a b
* DFA on the board
+-------+
| |b
v a |
O ----> o
^\
| \ b
+--+
* RE
* ab - Whoops. Doesn't work if it starts with a b
* (ab+|b)*
* (b*(ab)*b*)*
* (a?b)*
- Are we sure about that this derives b
(a?b)* => (a?b) => b
- Are we sure about that this derives bb
(a?b)* => (a?b)(a?b) => b(a?b) => bb
NFAs vs DFAs
* In DFAs, there is only (at most) one transition for any state/letter pair
* In NFAs, there can be multiple transitiosn for the same state/letter pair
* The string is in the language if there is SOME sequence that brings
you to the final state
* Normal question in language models: If we add nondeterminacy, do we gain
power?
* NP algorithms vs P algorithms: Current hypothesis: There are some
algorithms for which there is an NP algorithm, but not a P algorithm
* NFA vs DFA: Provably equivalent
* Side note: NFAs also add epsilon transitions: You can take this edge
without consuming an input token
Regular expression -> Code
* Regular expression -> NFA
* NFA -> DFA
* DFA -> 'Optimal' DFA
* DFA -> Code
Goal: Transform every regular expression into an NFA
* A special NFA: One start state, one stop state.
What kinds of regular expressions are there?
* Epsilon: epsilon
* Single character/symbol: s
* Alternation: (R1|R2)
* Concatenation: (R1R2)
* Kleene Star (R*)
See pictures
* On white board
* On outline
* In book