In
theoretical computer science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumsc ...
, Arden's rule, also known as Arden's lemma, is a mathematical statement about a certain form of
language equation Language equations are mathematical statements that resemble equation, 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 ...
s.
Background
A
(formal) language is simply a set of strings. Such sets can be specified by means of some
language equation Language equations are mathematical statements that resemble equation, 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 ...
, 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
In set theory, the union (denoted by ∪) of a collection of sets is the set of all elements in the collection. It is one of the fundamental operations through which sets can be combined and related to each other.
A refers to a union of ze ...
''A'' ∪ ''B'', and their
concatenation
In formal language, formal language theory and computer programming, string concatenation is the operation of joining character string (computer science), character strings wikt:end-to-end, end-to-end. For example, the concatenation of "sno ...
''A''⋅''B''. Finally, as an operation taking a single
operand
In mathematics, an operand is the object of a mathematical operation, i.e., it is the object or quantity that is operated on.
Example
The following arithmetic expression shows an example of operators and operands:
:3 + 6 = 9
In the above examp ...
, the set ''A''
* denotes the
Kleene star
In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. In mathematics,
it is more commonly known as the free monoid c ...
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
In mathematics, a linear equation is an equation that may be put in the form
a_1x_1+\ldots+a_nx_n+b=0, where x_1,\ldots,x_n are the variables (or unknowns), and b,a_1,\ldots,a_n are the coefficients, which are often real numbers. The coefficien ...
''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.
Equivalently, the set ''B''⋅''A''
* is the smallest language that is a solution for ''X'' in ''X'' = ''X''⋅''A'' ∪ ''B''.
Application
Arden's rule can be used to help convert some finite automatons to regular expressions, as in
Kleene's algorithm In theoretical computer science, in particular in formal language theory, Kleene's algorithm transforms a given nondeterministic finite automaton (NFA) into a regular expression.
Together with other conversion algorithms, it establishes the equival ...
.
See also
*
Regular expression
A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" or ...
*
Nondeterministic finite automaton
In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if
* each of its transitions is ''uniquely'' determined by its source state and input symbol, and
* reading an input symbol is required for each state tr ...
Notes
References
* Arden, D. N. (1960). Delayed logic and finite state machines, ''Theory of Computing Machine Design'', pp. 1-35, University of Michigan Press, Ann Arbor, Michigan, USA.
* (open-access abstract)
* John E. Hopcroft and Jeffrey D. Ullman, ''
Introduction to Automata Theory, Languages, and Computation
''Introduction to Automata Theory, Languages, and Computation'' is an influential computer science textbook by John Hopcroft and Jeffrey Ullman on formal languages and the theory of computation. Rajeev Motwani contributed to later editions begi ...
'', Addison-Wesley Publishing, Reading Massachusetts, 1979. {{ISBN, 0-201-02988-X. Chapter 2: Finite Automata and Regular Expressions, p.54.
*Arden, D.N. ''An Introduction to the Theory of Finite State Machines'', Monograph No. 12, Discrete System Concepts Project, 28 June 1965.
Formal languages