Formal Language

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:

1. There exists a DFA that specifies $L$
2. There exists an NFA without $ϵ$-transitions that specifies $L$
3. There exists an NFA with $ϵ$-transitions that specifies $L$
4. 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?

Related

• Context-Free Language