1. RE
	1. Find specified set of string in text
	2. A notation to specify a set of strings
	3. AB*A: zero or more occurance of B
	4. wildcard: .
	5. character class [A-Z]
	6. At least 1 A(BC)+DE
	7. exactly k [0-9]{5}-[0-9]{4}
2. NFAs
	1. Kleene’s algorithm: for any RE there is an DFA and vice versa
	2. Same as for KMP
		1. No backup in text input stream
		2. linear-time guarantee
		3. exponential number of states
	3. Nondeterministic finite state automata (NFA)
		1. Epsilon-transition (not deterministic)
		2. Accept if any sequence of transitions ends in accept state
		3. systematically consider all possible transitions
3. DFA Simulation
	1. State names: integers from 0 to M
	2. Match-transitions: keep regular rxpression in array re[]
	3. e-transitions: store in a digraph G
	4. Maintain all possible states that NFA could be in and reach to all possible states
	5. Accept if any state reachable is an accept state
	6. Reject otherwise
	7. Digraph reachability: directedDFS from each source, without unmarking vertices
		1. find all possibilities until leaf node
	8. MN worst case, average close to linear
4. NFA Construction
	1. Closure: single (go back to the previous state), after parenthesis (go back to previous parenthesis)
	2. Or: Add two e-transition edges for each |
	3. Use stack
	4. O(M)
5. RE Applications
	1. Grep
	2. crossword puzzles
	3. awk
	4. PERL (built on RE)
	5. Harvesting information
	6. Complexity attack: can implement RE do not guarantee performance to attack
	7. SpamAssasin RE
	8. \1 matches subexpression that was matched earier (periodic pattern)
	9. RE is the basis of compiler
	10. Worst-case of Java string.matches (exponential to N) (depending on the implementation details: this is on DFA with backtracking, also in Python re)