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