Arden's Rule

The lemma of Arden makes a statement about sets of character strings, which are the subject of theoretical computer science, more specifically, the theory of automata in the framework of formal languages .

5.1 Simple Examples
5.2 Complex Example

Formulation

It was an arbitrary alphabet; stand for the Kleene star, for the positive transitive closure, for the concatenation of two character-string sets and for whose ordinary unification ( in this priority - bracketing is neglected accordingly). Then the following equivalence holds:

Or the following equation:

In words: For any character-string set and a character-string amount, which does not contain the empty word, the equation has only one solution.

Evidence

On the quantization is evidence in both parts of the readability waived off half of what it is not very problematic for universal quantification, as long as no specifications for the variables in question are made. Corresponding points are treated specially.

Execution

It is a solution to the equation.

Superset

First, the definition of Kleene star is applied and used the distributivity of concatenation over Associations:

Now it can be shown by induction on, that applies to all:

Induction hypothesis

Induction beginning

Induction step

As for different n are all pairwise disjoint, follows the original superset relationship.

Subset

Here the proof is indirect: It is believed does not apply, so there must be at least one word with. Because is also an element of or must be formulated differently. In the first case consists of two pieces of words, and together, ie. Since it can not be the empty word ( the quantification calls ) follows. Considering the smallest of the adopted as existing, then would also have to apply, but this is contrary to the assumption. In the other case, ie, also yields the contradiction. Since both cases end in contradictions, the assumption must have been wrong, that does not apply.

Reverse direction

This proof direction is trivial, since it suffices to show that the equation solves all:

Application

The central importance of the Arden- lemma is its application in the theory of automata. It facilitates the determination of the amount of technical description, of a non -deterministic finite automata ( NFA ) accepted language:

Consider a NEA, whose states are to be identified with the natural numbers from to ( ie ). In addition, the following definitions are used:

With the help of these quantities can be part of the language of each state specify:

Is obtained by defining a system of equations with equations:

Now bringing a part of speech in a suitable form which allows an application of Lemma:

According to Arden's Lemma, this statement is equivalent to the following:

This solution is unique. If you place one in all the other equations, we obtain a system of equations with one variable less can simplify in this way more and more to the trivial case in which only one equation is left, which is independent of all other sub- languages can solve. By reverse - insertion and the rest of languages is then obtained to finally determine the unique solution to the entire equation system and to identify with the language accepted by the machine.

Algebraic viewing

From the perspective of abstract algebra represents the structure of a Dioids, which means that form both a distributive and monoids is about. The neutral element with respect to the union is the empty set and the neutral element with respect to the concatenation is. Due to the lack of invertibility, it is generally not possible to solve equations over this structure. The lemma of Arden allows at least to determine the solutions of some special equations and even unique.