[GAP Forum] Question about semigroup and finite-state machine

Serge teron at udm.ru
Wed Feb 22 18:57:54 GMT 2006

```Hello.

My problem is simple, but it is very urgent and
unfortunately I cannot solve it myself.
I have a task: There is a jump table of finite-state
machine. I must calculate
the semigroup of this FSM.
Following information is known:
1. Alphabet of FSM, set of initial and final states are the
same
2. Size of jump table is limited to 5*5

As far as I know, semigroup of finite-state machine is the
set of congruence classes of its elements.
In my case, FSM is representation from A*A to A (f: AA ->
A), where A is alphabet, set of initial and final states.
I thought that AA means Cartesian product, or in this case
second Cartesian power of set A, but I was wrong.

So, the first question is:
Can anyone explain, how should I treat record AA?

According to the definition of congruence relation, x is
congruent to y, if they are equivalent and
for any t xt is equivalent to yt and tx is equivalent to
ty. According to the definition of semigroup of
machine, t1 is congruent to t2 if for all a and b from AA
f(at1b)=f(at2b), where f is our machine.

The second question is:
How should I apply machine to the string? My teacher said
that at1b is concatenation of strings, but
I am still unclear, how to calculate f(at1b).

And the last question:
My teacher recommends me to use GAP in order to solve this
task. But I didn't use GAP earlier.
Can you tell me, which advantages I receive, if I will use

Any help is appreciated. Thank you in advance.