State Machines II: An Exercise with Automatons

Solving Problems With 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: In this worksheet we give two solutions for the following Exercise:

Create automaton accepting all nonzero binary numbers which can be divided by 4.

Introduction: The solution of this simple but hopefully nontrivial excercise creates us the possibility to demonstrate the usage of several procedures of aut package.

Section I: Solution 1

> with(aut):

First of all we use Maple to suspect, which binary numbers can be devided by 4.

> for i to 10 do
printf("%2d %8s\n",4*i,convert(convert(4*i,binary),string))
od:

 4      100

 8     1000

12     1100

16    10000

20    10100

24    11000

28    11100

32   100000

36   100100

40   101000

Notice that all the binary numbers end with two 0s. It is easy to prove that this conjecture is true, i.e. a nonzero binary number can be devided by 4 if and only if it ends with two 0s.

According to the above remark, we have to build automaton which accepts words ending with two 0s. These words have the form q00, where q is arbitrary word over the alphabet {0,1}.

First we define automaton which recognizes all words over the alphabet {0,1}. The automaton has one state only, which is intial state and final state at the same time.

> Xi:=genaut([a,0,a,a,1,a],a,a):
plotaut(Xi);

Now add two new transitions to automaton and let`s denote the resulting automaton by . We can perform this step by using the procedure addaut . The first parameter of addaut is the automaton itself. The second parameter describes two new transitions. The third parameter defines new final state f.

> Xi1:=addaut(Xi,transition={[a,`0`,b],[b,`0`,f]},fin=f):
plotaut(Xi1);

We feel is the solution of our excercise. Let see the language accepted by . The procedure langaut dislpays a finite subset of the language.

> langaut(Xi1,1..4);

This result is a little bit disappointing. In fact all words over the alphabet {0,1} are accepted. This is because the state `a` remained final state. Let`s delete `a` from set of final states.

> Xi2:=delaut(Xi1,fin=a):printaut(Xi2);

> langaut(Xi2,0..5,lexorder);

Much better. We are, however, not very happy to see leading 0s. We have to provide that accepted words should begin with `1`. This can be solved by introducing a new initial state. On the same time `a` has to be erased from inital states.

> Xi3:=addaut(delaut(Xi2,ini=a),tra=[A,`1`,a],ini=A):
plotaut(Xi3);

The next command shows that leading zeros disappeared...

> langaut(Xi3,0..5);

.. whilst the procedure Analyze produces the regular expression for the language accepted by . The result of Analyze does not need explanation.

> Analyze(Xi3);

Notice that automaton is not deterministic. If we would need deterministic automaton, we can use the procedure Adeterm .

> Xi4:=Adeterm(Xi3);

Maple recognizes as being of type deterministic.

> type(Xi4,deterministic);

Next command shows that automata and accept the same language, i.e. they are equivalent.

> Aequi(Xi3,Xi4);

The set of state of is the powerset of the ste of states of , as we can see on the transition matrix of .

> printaut(Xi4);

In order to encrease readibility, we can rename the states of , while keeping all the transitions unchanged. In other words we create isomorph automaton. The procedure Aisomorph displays the way of coding if we use the option code .

> plotaut(Aisomorph(Xi4,code));

>

Section II: Solution 2

The second solution of our excercise is based on the perception that the language of binary numbers, which terminate with two zeros equals to the product of three languages: {1},{0,1}*,{00}.

The one element language {1} can be recognized by automaton . Notice that we gave a fourth parameter of genaut, which is the alphabet of input signals. This is necesssary, as no transitions are defined for input signal `0`.

> xi1:=genaut([a,1,f],a,f,genabc({0,1})): printaut(xi1);

The automaton accepts the language {0,1}* is created in in the next comand

> xi2:=genaut([a,1,a,a,0,a],a,a): printaut(xi2);

In the end the one element language {00} can be accepted by automaton .

> xi3:=addaut(genaut([a,0,b,b,0,f]),input=`1`): printaut(xi3);

The automaton we are looking for can be generated by procedure Aproduct .

> Phi:=Aproduct(Aproduct(xi1,xi2),xi3);

By default the procedure plotaut places the nodes of transition graph on the onto a circle, whose radius equals to 1. This however does not always results in nice pictures. For this reason plotaut allows us to use option of the form s=[c1,c2], where s is the name of a state, c1 and c2 are numbers. This option prescribes plotaut that the node representing the state s has to have coordinates [c1,c2].

> plotaut(Phi,a=[-1,-1],b=[-1,1],c=[0,1],0=[1,1],1=[1,0],2=[1,-1]);

Automaton serves another solution for our excercise. It has six state, while automaton (see Solution 1.) has four state only. From this point of view is better solution. Of course and are equivalent.

> Aequi(Xi3,Phi);

Let us end this worksheet by a nice animation. Notice that the procedure accept allows us to specify the option animate. By using amimate we prescribe accept to create amination which visualizes the process of recognition of input words. Besides animate we can use all the options of plotaut. In this case we specified the coordinates of different states.

It worth mentioning that automaton Phi has -transitions.Observe how the next set of possible states are computed first and after that the -closure of this set is created. Have fun.

> accept(Phi,`10100`,animate,a=[-.8,-1],b=[-.8,1],c=[0,1],0=[.8,1],1=[.8,0],2=[.8,-1]);

>