State Machines I - Automatons Background

Notions and Their Implementation in the aut Package

by Gyorgy Maroti, Zenon Computer Engineering and Trading Ltd., Hungary, maroti@zenon.hu,

< 2000 Gyorgy Maroti, Zenon Computer Engineering and Trading Ltd.>

NOTE: This woksheet gives a short introduction to the usage of the aut package. It summarizes the most important notions of automata theory and shows how they are implemented in Maple. Althought several procedures of the package are touched, this presentation is neither a tutorial, nor a coursebook. The procedures appear in this worksheet are used in their simplest form. All of them have several options (extra parameters), which make the usage of the procudures easier and more flexible.

Introduction: Definition of Automata

Automaton is a five element list Xi=[S, X, , Q, F], where

1. S is a finite nonempty set. The elements of S are called the states of automaton Xi.

2. X is a finite nonvoid set of type alphabet . The elements of X are called the input signals of automaton Xi.

3. is a table (in Maple sence), which desribes a pactial function Sx(X union {e}) -> P(S). is called the transition
function of automaton Xi.
If [a,v]=A for some state `a` and input signal `v`, then we call A the next set of possible states . Notice, A is
not necessarily defined. On the other hand A may be defined as the empty set.
If [a,e]=A for some state `a`, then we say the automaton has - transitions , i.e. the automaton is able to change its
state without getting input signal.

4. Q is an (empty or nonempty) subsetof S, the set of initial states .

5. F is an (empty or nonempty) subset of S, the set of final states .

Section I: Establishing Automaton `by hand` - Never Again !

> restart;libname;

> with(aut):

Note: the aut.m file that is available for download must be placed in one of your recognized "lib" directories.

Define the set of state ...

> S:={a,b,c};

... and the set of input signals...

> X:={x,y};type(X,alphabet);

... and the transition funtion (a table in Maple sence)...

> delta[a,x]:={a,b};
delta[a,y]:={b};
delta[b,e]:={a};
delta[b,x]:={c};

... and the automaton itself by creating a five element list.

> Xi:=[S,X,delta,{a},{c}];

Our effort is successful, as Maple recognizes Xi as a type automaton .

> type(Xi,automaton);

Section II: aut Package Offers the Procedure genaut

The process above is not only time consuming, but also the steps we made had redundancy. Indeed, the transition fuction itself contains the relevant states and input signals.The independent listing of states and input signal seems not to be necessary. The procedure genaut collects all the states and input signals, which appear in , and creates the set of states and the set of input signals.

> Phi:=genaut(delta,a,c);

The result is automaton Phi...

> type(Phi,automaton);

...whose details can be seen on its transition matrix.

> printaut(Phi);

>

Section III: Different Types of Automata

The aut package contains three futher types concerning automata: emptyfree, deterministic, complete.
If the transition function of automaton Xi is a pactial function SxX->P(S) then Xi is called emptyfree .

If the automaton is emptyfree and the image set for all pairs of SxX has at most one element or not defined, then we call the automaton deterministic .

If the image set for all pairs of SxX has at least one element, then we call the automaton complete .
As an example let see the properties of automaton Xi, defined above.

Xi is not emptyfree, as it has one -transition.

> type(Xi,emptyfree);

Xi is not deterministic, as delta(a,x) has two elements.

> type(Xi,deterministic);

Xi is not complete, as e.g. delta(b,y) is not defined.

> type(Xi,complete);

All these properties can be easily checked by displaying the transition graph of Xi. We use the plotaut procedure of aut package.

> plotaut(Xi);

>

Section IV: How to describe the operation of automata?

Before answering the question above, we have to introduce the notion of - closure .
Let A be a subset of states. If we form the union of A and sets [a,e] for all state a of A, we obtain the set A[1] which contains A. Repeat the process for A[1], and create the set A[2], etc. In this way we obtain a sequence of sets

A < A[1] < A[2] <...

As all of these sets are subset of S, wich is finite, there must be an index i such that

A < A[1] < A[2] <...< A[i] = A[i+1] =...

The set C:=A[i] is called the -closure of the set A. Notice that -closure consists of all states, which are reachable from the states of A through one ore more -transitions.

The -closure of the set A can be created by the procedure closure .

> closure(Phi,{b});

If there is no -transition defined for the states belong to a set A, then the -closure of A equals to itself.

> closure(Phi,{c});

>

The operation of an automaton is described by procedure Delta .

1. Delta is a function of three argument:

Xi - automaton,

A - subset of the set of states of Xi,

w - word over the input signals of Xi.

2. Delta (Xi, A, ) equals to the closure (Xi, A), i.e. -closure of the set A.
3. For the input signal x, Delta (Xi, A, x) equals to the -closure of the union of sets [s, x], where s is elemet of
Delta (Xi, A, ).

4. If w=px then Delta (Xi, A, w) equals to Delta (Xi, Delta(Xi, A, p), x).

As our notion of automaton is nondeteministic, we speak about sets of possible states . At the very beginning of operation the set of possible states S[0] equals to Q, the set of initial states. The first input signal v1 comes and we define the next set S[1] of possible states as S[1]:= Delta (Xi, S[0], v1). Obtaining the next input signal v2, we define S[2]:= Delta (Xi, S[1], v2) as the next set of possible states, etc.

As an example we show the sequence of possible states, when the automaton gets the input word `xyx`.

Let S0, the set of first possible state, equal to the set of initial states.

> S0:={b};

The first input signal is x comes and the next set of possible states is S1.

> S1:=Delta(Phi,S0,x);

The second input signal is y comes and the next set of possible states is S2.

> S2:=Delta(Phi,S1,y);

In the end the third input signal is x again and the resulting set of possible states is S3.

> S3:=Delta(Phi,S2,x);

These three steps can be evaluated in one step.

> Delta(Phi,S0,xyx);

Delta becomes moe communicativ, if we give the option trace1. More specifically, with trace1 Delta lists of all sets of possible states.

> Delta(Phi,S0,xyx,trace1);

-Delta begins with {b}

-Delta({b, a},x) = {b, a, c}

-Delta({b, a, c},y) = {b, a}

-Delta({b, a},x) = {b, a, c}

We obtain futher details of the computation by using the option trace2.

> Delta(Phi,S0,xyx,trace2);

-Delta begins with {b}

 .{b},closure ->{b, a}

-Delta({b},e) = {b, a}

 .b,x->{c}

 .a,x->{b, a}

-Delta({b, a},x) = {b, a, c}

 .a,y->{b}

 .{b},closure ->{b, a}

-Delta({b, a, c},y) = {b, a}

 .b,x->{c}

 .a,x->{b, a}

-Delta({b, a},x) = {b, a, c}

>

Section V: Accepting Language by Automaton

We say the automaton Xi accepts the word w if the intersection of sets Delta (Xi, X[4], w) and Xi[5] (the set of final state) is nonvoid. In other words, the automaton begins its operation with the set of initial states. This is the first set of possible states. After that Delta (Xi, X[4], w) determines the set of possible states by processing the word w. If this set of possible states possesses at least one final state, we say that w is accepted . Otherwise w is said not to be accepted by Xi. The language L accepted by automaton Xi consists of all words accepted by Xi.These functionalities are implemented by the procedures accept and genlang.

Automaton Phi accepts the word xyy.

> accept(Xi,xyx);

If we want to show the details of computation, we use options trace1 and show of accept .

> accept(Xi,xyx,trace1,show);

-Delta begins with {a}

-Delta({a},x) = {b, a}

-Delta({b, a},y) = {b, a}

-Delta({b, a},x) = {b, a, c}

Result of Delta:

Result of accept:

The process of recognition can be vizualise by using the option animate. The animation below show how the automaton process the input word xyx. In order to be able to see the different action, it is practical to see the pictures step by step.

> accept(Xi,xyx,animate);

The word xy is not accepted by automaton .

> accept(Xi,xy,trace2,show);

-Delta begins with {a}

 .a,x->{b, a}

-Delta({a},x) = {b, a}

 .a,y->{b}

 .{b},closure ->{b, a}

-Delta({b, a},y) = {b, a}

Result of Delta:

Result of accept:

The language accepted by automaton is not necessarily finite. For that reason the procedure langaut work in such a way that it shows a finite subset of the accepted language.

> langaut(Phi);

By default langaut dislpays the words of length less then or equal to 3. We can, however, control not only the length of words, but also the way of ordering.

> langaut(Phi,2..4,lexorder);

>