Loading AI tools
From Wikipedia, the free encyclopedia
In theoretical computer science, Arden's rule, also known as Arden's lemma, is a mathematical statement about a certain form of language equations.
This article needs additional citations for verification. (March 2010) |
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 A ∪ B, and their concatenation A⋅B. Finally, as an operation taking a single operand, the set A* denotes the Kleene star of the language A.
Arden's rule states that the set A*⋅B is the smallest language that is a solution for X in the linear equation X = A⋅X ∪ B 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]
Equivalently, the set B⋅A* is the smallest language that is a solution for X in X = X⋅A ∪ B.
Arden's rule can be used to help convert some finite automatons to regular expressions, as in Kleene's algorithm.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.