Arden's Rule

In theoretical computer science, Arden's rule, also known as Arden's lemma, is a mathematical statement about a certain form of language equations.

Background

A (formal) language is simply a set of strings. Such sets can be specified by means of some language equation, which in turn is based on operations on languages. Language equations are mathematical statements that resemble numerical equations, but the variables assume values of formal languages rather than numbers. Among the most common operations on two languages A and B are the set union AB, and their concatenation AB. Finally, as an operation taking a single operand, the set A* denotes the Kleene star of the language A.

Statement of Arden's rule

Arden's rule states that the set A*B is the smallest language that is a solution for X in the linear equation X = AXB where X, A, B are sets of strings. Moreover, if the set A does not contain the empty word, then this solution is unique. [1][2]

See also

Notes

  1. Daintith, John (2004). "Arden's Rule". Archived from the original on 13 February 2010. Retrieved 10 March 2010.
  2. Sutner, Klaus. "Algebra of Regular Languages" (PDF). Retrieved 15 Feb 2011.

References

This article is issued from Wikipedia - version of the 11/9/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.