Regular Languages

Definitions

• DFA
• DFA accepted string
• Regular language
• Regular operations (union, concat, star)

Theorems

• Closure under union
• Closure under concatenation

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.