- A finite automaton (dfa or nfa).
- A regular expression.
- A regular grammar.

**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.

**Proof.** Construct the language

Copyright © 1996 by David Matuszek

Last modified Feb 24, 1996