Regular Languages and Kleene's Theorem

Theorem

The following statements are equivalent:

  1. There exists a DFA that specifies the language
  2. There exists an NFA without ε-transitions specifying
  3. There exists an NFA with -transitions specifying
  4. There exists a regular expression specifying

Languages that can be specified by a DFA, NFA, or regular expression are regular languages