Ardens rule

views updated

Arden's rule A formal language can be specified by means of equations, based on operations on languages. Arden's rule states that A*B is the smallest language that is a solution for X in the linear equation X = AX B

where X, A, B are sets of strings. (For notation, see union, concatenation, Kleene star.) A*B is furthermore the only solution, unless A contains the empty string, in which case A*B′ is a solution for any subset B′ of B.

Although simple, Arden's rule is significant as one of the earliest fixed-point results on equation solving in computer science. In conjunction with the normal process of eliminating variables, it can be used to solve any set of simultaneous linear equations over sets of strings. See also Kleene's theorem (on regular expressions).