Regular Languages
Finite Automata
Definitions
- DFA
- DFA accepted string
- Regular language
- Regular operations (union, concat, star)
Theorems
- Closure under union
- Closure under concatenation
Nondeterminism
In a deterministic machine, we can always determine the next state. In a nondeterministic machine there may be several possible next states which must all be considered. This means that DFA's are a subset of NFA's.
Definitions
- NFA definition
Theorems
- Equivalence of NFA and DFA
- Closed under union, concatenation and star
We must understand how to convert an NFA to a DFA.