[Overview] [Previous] [Next]

# Standard Representations

A regular language is given in a standard representation if it is specified by one of:
• A finite automaton (dfa or nfa).
• A regular expression.
• A regular grammar.
(The importance of these particular representations is simply that they are precise and unambiguous; thus, we can prove things about languages when they are expressed in a standard representation.)

Membership. If L is a language on alphabet , L is in a standard representation, and w *, then there is an algorithm for determining whether w L.

Proof. Build the automation and use it to test w.

Finiteness. If language L is specified by a standard representation, there is an algorithm to determine whether the set L is empty, finite, or infinite.

Proof. Build the automaton.

• If there is no path from the initial state to a final state, then the language is empty (and finite).
• If there is a path containing a cycle from the initial state to some final state, then the language is infinite.
• If no path from the initial state to a final state contains a cycle, then the language is finite.
Equivalence. If languages L1 and L2 are each given in a standard representation, then there is an algorithm to determine whether the languages are identical.

Proof. Construct the language

(L1 -L2) (-L1 L2)
If this language is empty, then L1 = L2. (Why?)