====== 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.
===== Regular Expressions =====

===== Nonregular Languages =====