A regular language is a formal language (i.e. a possibly infinite set of finite sequences of symbols from a finite alphabet) that satisfies the following equivalent properties:
All finite languages are regular. Other typical examples include the language consisting of all strings over the alphabet {a, b} which contain an even number of a's, or the language consisting of all strings of the form: several a's followed by several b's.
The result of the union, intersection and setdifference operations when applied to regular languages is itself a regular language; the complement of every regular language is a regular language as well. Reversing every string in a regular language yields another regular language. Concatenating two regular languages (in the sense of concatenating every string from the first language with every string from the second one) also yields a regular language. The shuffle operation[?], when applied to two regular languages, yields another regular language. The right quotient and the left quotient[?] of a regular language by an arbitrary language is also regular.
To locate the regular languages in the Chomsky hierarchy, one notices that every regular language is contextfree. The converse is not true: for example the language consisting of all strings having the same number of a's as b's is contextfree but not regular. To prove that a language such as this is not regular, one uses the pumping lemma.
There are two purely algebraic approaches to defining regular languages. If Σ is a finite alphabet and Σ* denotes the free monoid over Σ consisting of all strings over Σ, f : Σ* > M is a monoid homomorphism[?] where M is a finite monoid, and S is a subset of M, then the set f^{ 1}(S) is regular. Every regular language arises in this fashion.
If L is any subset of Σ*, one defines an equivalence relation ~ on Σ* as follows: u ~ v is defined to mean
Search Encyclopedia

Featured Article
