- Rochester Math Olympiad
- Western NY regional math problem-solving contest
- 4 problems in 3 hours
- Small cash prizes for top 3 finishers in region
- Feb. 6 (this Saturday), 9:30 - 12:30
- See Prof. Towsley to join
- Section 1.3 “Equivalence with Finite Automata”
- Theorem: language regular iff described by regular expression
- Proof, part 1: convert regular expression to NFA
- Construction from 6 cases in regular expression definition
- Examples of how to build NFAs, using constructions from closure proofs
- Proof, part 2: construct regular expression from DFA
- Use GNFA
- GNFA start state transits to every other state but nothing transits to it
- Only 1 accept state, with transitions from everything else and no outgoing transitions
- Transitions between all pairs of non-start, non-accept states
- Convert DFA to GNFA
- Find regular expression for GNFA, from reduced GNFA
- Use GNFA
- Examples / questions
- Does GNFA construction work for NFAs as well as DFAs?
- Yes, no reliance on determinism in proofs
- Automaton constructed from NFA in problem set 1,
problem 3
- Does GNFA construction work for NFAs as well as DFAs?
- Problem set
- Finish NFA-to-regular-expression example above
- Mini-assignment: see if you can finish it on your own