teaching machines

CS 330 Lecture 4 – Regex to NFA to DFA to fail

January 30, 2012 by Chris Johnson. Filed under cs330, lectures, spring 2012.

Agenda

• how to implement a regex engine
• what’s an NFA?
• converting a regex to an NFA
• converting an NFA to a DFA
• the limits of DFA-recognized languages
• the pumping lemma
• context-free grammars
• balancing parentheses
• a calculator language
• parse tree

Regex to NFA

• concatenation
• alternation
• Kleene star

NFA to DFA

• DFA’s start state is set of all states accessible from NFA’s start state with epsilon transition
• for each state q in DFA

• for each symbol x in alphabet
• get set of states accessible from q’s NFA states after an x transition
• augment it by the set of states accessible from these by epsilon transitions
• add this state to our DFA, with a transition from q to it by symbol x

Reference

• http://www.codinghorror.com/blog/2009/11/parsing-html-the-cthulhu-way.html

Haiku