[Overview] [Previous] [Next]

Standard Representations

A regular language is given in a standard representation if it is specified by one of: (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 sigma, L is in a standard representation, and w is a member of sigma*, then there is an algorithm for determining whether w is a member of 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.

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 intersection -L2) union (-L1 intersection L2)
If this language is empty, then L1 = L2. (Why?)


Copyright 1996 by David Matuszek
Last modified Feb 24, 1996