teaching machines

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

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

Haiku

DFAs are dumb
I socked one hard in Q Bar
Next night, he hugged me!

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *