Encyclopedia > Regular language

  Article Content

Regular language

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 set-difference 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 context-free. The converse is not true: for example the language consisting of all strings having the same number of a's as b's is context-free 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

uw in L if and only if vw in L for all w in Σ*
The language L is regular if and only if the number of equivalence classes of ~ is finite; if this is the case, this number is equal to the number of states of the minimal deterministic finite automaton accepting L.

External resource

  • Department of Computer Science at the University of Western Ontario: Grail+, http://www.csd.uwo.ca/research/grail/. A software package to manipulate regular expressions, finite-state machines and finite languages. Free for non-commercial use.

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
Great River, New York

... 70.9% are married couples living together, 7.3% have a female householder with no husband present, and 17.9% are non-families. 13.4% of all households are made up of ...

This page was created in 53.2 ms