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 , the following statements are equivalent:

  1. There exists a DFA that specifies
  2. There exists an NFA without -transitions that specifies
  3. There exists an NFA with -transitions that specifies
  4. There exists a Regular Expression that specifies

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?