## 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!

I socked one hard in Q Bar

Next night, he hugged me!