Arden's Rule
Encyclopedia
In theoretical computer science
, Arden's rule, also known as Arden's lemma, is a mathematical statement about
a certain form of language equation
s.
is nothing else then 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.
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.
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
, Arden's rule, also known as Arden's lemma, is a mathematical statement about
a certain form of language equation
Language equation
Language equations are mathematical statements that resemble numerical equations, but the variables assume values of formal languages rather than numbers. Instead of arithmetic operations in numerical equations, the variables are joined by language operations...
s.
Background
A (formal) languageFormal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
is nothing else then a set of strings. Such sets can be specified by means of some language equation
Language equation
Language equations are mathematical statements that resemble numerical equations, but the variables assume values of formal languages rather than numbers. Instead of arithmetic operations in numerical equations, the variables are joined by language operations...
, 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
Operand
In mathematics, an operand is the object of a mathematical operation, a quantity on which an operation is performed.-Example :The following arithmetic expression shows an example of operators and operands:3 + 6 = 9\;...
, the set A* denotes the Kleene star
Kleene star
In mathematical logic and computer science, the Kleene star is a unary operation, either on sets of strings or on sets of symbols or characters. The application of the Kleene star to a set V is written as V*...
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 equationLinear equation
A linear equation is an algebraic equation in which each term is either a constant or the product of a constant and a single variable....
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.