# Kleene’s Theorem

Kleene’s theorem tells us that DFAs, NFAs with and without $ϵ$-transitions, and regular expressions all have the same expressive power: for a language $L$, the following statements are equivalent:

- There exists a DFA that specifies $L$
- There exists an NFA without $ϵ$-transitions that specifies $L$
- There exists an NFA with $ϵ$-transitions that specifies $L$
- There exists a Regular Expression that specifies $L$

Languages that can be specified by a DFA, NFA, or Regular Expression are called **regular languages**.

In our Compiler for CS241E, we use a Regular Language for the process of Scanning.

What are examples of language that is not regular?

- The language of words of balanced parentheses is an example of a context-free but nonregular language.
- The language of words with arithmetic expressions with parentheses.
- The language of words with an equal number of occurrences of a and b is yet another example.

**Generally, any language that allows for “nesting” will not be regular** → So any language that is ambiguous?