DFA, NFA, Regular Languages

1. Using deterministic finite automata (DFAs).
2. Using nondeterministic finite automata (NFAs).
3. Using a closure definition involving, union, concatenation, and Kleene ∗.
4. Using regular expressions.
5. Using right-invariant equivalence relations of finite index (the Myhill-Nerode charac-
   terization).
6. Using right-linear context-free grammars.

• DFA
• NFA

closure

regular expressions

right-invariant equivalence relations of finite index

DFA

The “Cross-product” Construction

Morphisms, F-Maps, B-Maps and Homomorphisms of DFA’s

NFA

smallest DFA

transition table $\delta$

值的格子是集合，多一列Epsilon输入，不接受Epsilon移动的状态这里就是空集合

$\epsilon$-Closure

Converting an NFA into a DFA

An Algorithm to convert an NFA into a DFA: The “subset construction”

Finite State Automata With Output: Transducers

An Application of NFA’s: Text Search