Kleenes theorem

views updated

Kleene's theorem
1. on regular expressions. A theorem in formal language theory proposed by S. C. Kleene and stating that a language is definable by a regular expression if and only if it is recognized by a finite-state automaton. A regular expression equivalent to a finite-state automaton can be found by solving a set of simultaneous linear equations (see linear grammar, Arden's rule). Regular expressions were first used to characterize the power of certain neural networks.

2. on fixed points. See fixed-point theorem.