Automata

Collaboration diagram for Automata:

Automaton constructs for Vaucanson. More...


Files

file  automata_ops.hh
 This file holds the default operations for the elements of the automata set.

Namespaces

namespace  vcsn::automata
 Namespace for automata constructs in Vaucanson.

Modules

 Concept
 Operators on automata

Classes

struct  AutomataBase
 It symbolises the set of automata with multiplicity over a fixed semiring and a fixed free monoid. More...
struct  TransducerBase
 The most general concept of transducer. More...

Detailed Description

Automaton constructs for Vaucanson.

See also:

Theoretical context

The striking feature of automata is the versatility of the concept - a labeled oriented graph - and its ability to models so many different kinds of machines simply by varying the domains where the labels are taken.

This chapter presents the kinds of automata Vaucanson has been designed to work on. First, naive definitions are given to remind the reader what is a Boolean automaton from a theoretical point of view. Then, more elaborated definitions are given to provide a generalized context in which it is possible to define weighted automata. Finally, this chapter explains how this formalism is used to represent transducers. The interested reader may find far more advanced descriptions and definitions in 03sakarovitch.

Boolean automata

This section gives some well known definitions about Boolean automata. Those should be rather usual to the experienced reader. A first definition introduces basic letter automata while a second one presents Boolean automata with spontaneous transitions.

Letter automata

Definition 1   A Boolean letter automaton is a 5-tuple
img5.png
with:

Figure 1.1: A simple Boolean automaton recognizing the language of words which contain a b.
b1.png

Figure 1.2: A Boolean automaton recognizing the language of binary numbers that are divisible by 3 (with a as 0 and b as 1).
div3-bool.png

Figures 1.1 and 1.2 show some examples of Boolean automata. A word

img10.png
of length
img11.png
is said to be recognized by an automaton
img4.png
if there exist a path from an initial state to a final state labeled with the word, i.e. a sequence of
img11.png
consecutive transitions

img12.png

with

  1. img13.png
    ,
  2. img14.png
    ,
  3. img15.png
    ,
  4. img16.png
    .

Spontaneous transitions

It is common to add to the previous definition the ability for an automaton to have ``spontaneous transitions''. Such transitions are not labeled by any letter and can be ``triggered'' at any time during the evaluation of an automaton. This give definition 2.

Definition 2   A Boolean automaton with spontaneous transitions is a 6-tuple

img17.png
with:
  • img5.png
    an alphabet,
  • img6.png
    a finite set of states,
  • img7.png
    a set of transitions,
  • img18.png
    a set of spontaneous transitions,
  • img8.png
    a set of initial states, and
  • img9.png
    a set of final states.


The evaluation of such an automaton is performed as for other letter automata, but spontaneous transitions may be part of the path.

Weighted automata

Boolean automata are devices designed to recognize and represent a particular class of languages. This section introduces another class of automata that are able to perform some computations on words instead of just recognizing them. This class is the class of weighted automata. First, the concept is presented and then a more complete formalism will be given.

Basis

Basically, the transitions of weighted automata are labeled with a weight and a letter. Initial and final states are also labeled with a weight. For a given path from an initial to a final state, it is possible to compute a value. Each weight of the path is multiplied, including the weights from the initial and the final state. An example is given in figure 1.3.

Figure 1.3: Evaluation with a deterministic weighted automaton.
[-1cm]
weighted-dummy.png

img19.png

When a weighted automaton is deterministic, its evaluation for a given word is straightforward. Either there exists a unique path labeled with the evaluated word from an initial state to a final one, and the result is computed as explained above, either there exist no such path and the result evaluates to zero.

However, with non-deterministic weighted automata, there may exist several paths from an initial to a final state that are labeled with the same word. In that case, such a word evaluates to the sum of the evaluation of each path. An example is given in figure 1.4.

Figure 1.4: Evaluation with a non-deterministic weighted automaton.
b3-bred.png

img20.png


This weighted automaton computes the value of a number from its binary representation. Thus, if a is considered to be 0 and b to be 1, the word babb (1011) evaluates to 11.

Furthermore, it is not mandatory for a weighted automaton to use the usual addition and multiplication. In fact the weight may be in any set, provided it is equipped with two internal laws that provide the structure of a semiring, as defined in 3.

Definition 3  
img21.png
is a semiring, if and only if:

A weighted automaton is always defined over a particular semiring. It is worth noting that ``Classical'' Boolean automata are just weighted automata over
img29.png
that maps a letter
img30.png
to true if a transition exists on
img30.png
.

This gives definition 4.

Definition 4   A
img31.png
weighted letter automaton is a 6-tuple
img32.png
with:

Series as labels

Definition 4 does not provide any support for spontaneous transitions. However, transitions on automata are not necessarily letter or spontaneous transitions. They may be polynomials (e.g.
img36.png
) or even rational expressions (e.g.
img37.png
). In a more general way transitions are defined to be series, as given in definition 5.

Definition 5   A series from a monoid
img38.png
to a semiring
img31.png
, noted as an element of the set
img39.png
, is an application which maps elements of
img38.png
to elements of
img31.png
.

The smallest set that contains all polynoms on
img38.png
with coefficients into
img31.png
and which is closed using the star operation is the set of

img31.png
-rational series on
img38.png
, noted
img40.png
.

At a basic level, rational series may be used to define rational languages. Thus a Boolean series in
img41.png
which maps words from a free monoid
img42.png
over an alphabet
img5.png
to Boolean values true or false may be viewed as an indicator function for a language.
img41.png
is exactly the set of rational expressions on the alphabet
img5.png
.

Equipped with those definitions, it is now possible to formally define an automaton.

Definition 6   A
img31.png
-automaton is a 6-tuple
img43.png
with:

Using definition 6, a letter transition for a Boolean automaton is a transition labeled by a series that maps a specific letter to true and everything else to false. A spontaneous transition is a transition which support is the empty word and a weighted letter transition is a transition which support has one unique letter.

In the particular case where
img47.png
(with
img5.png
an alphabet),
img48.png
and each transition's label is just a letter, we fall back in the ``usual case'' of ``traditional'' Boolean automata.

Of course this definition covers a wide variety of automata. In particular, note that the ``input'' of the automaton is not necessarily a free monoid. Therefore, it is not required for inputs to be decomposable in letters in a unique fashion. Also, there is no special restriction on an automaton transition's labels. Typically these labels are just letters, but nothing prohibits them to be words or even rational expressions. Such an automaton is shown in figure 1.5.

Figure 1.5: The automaton of figure 1.4, with rational expressions as labels.
b4.png

The evaluation of such an automaton for a given input is not possible in general. When
img38.png
is a free monoid, each member of it (so called words) is decomposable into a unique sequence of letters, and the evaluation may be defined in the case transitions are also labeled with letters.

As will be seen in the next section, definition 6 is general enough to include transducers, provided good monoids and semirings are used. To ensure a maximal genericity and mathematical consistency, VAUCANSON uses this definition to work on any kind of Boolean automata, weighted automata or transducers.

Transducers

Transducers are a special kind of automata that are designed to ``translate'' rational languages into other rational languages. While the evaluation of a weighted automaton gives weights, the evaluation of a transducer gives another word. The input alphabet and the output alphabet are not necessarily equal. An example of transducer is given in figure 1.6.

Figure 1.6: A transducer that divides binary numbers by 3.
div3-trans.png


On the graphical representation of a transducer, the letters on the left hand side of | represent the input letters and the letters on the right hand side represent output letters.

This transducer works on the alphabet

img49.png
. It expects a binary number as input, a being the digit 0 and b being the digit 1. The output consists in the binary representation of the input divided by 3. As an example, bba (110 or 6) gives abb (010 or 2).

Using the formalism of definition 6 it is possible to define transducers in two different ways:

Of course, a transducer may have arbitrarily complex labels, as shown in figure 1.7. In this example, some initial or final states do produce output and some transitions may produce several letters as output.

Figure 1.7: A complex transducer which replaces every occurrence of abb with yxx.
fibo-left.png

Transducers are currently being implemented in VAUCANSON. Although it is possible to build transducers and run various algorithms on them, their support is less complete than for other automata. 04oconnor provides information about the implementation of transducers in VAUCANSON.

Generated on Sun Jul 29 19:47:34 2007 for Vaucanson by  doxygen 1.5.2