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

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


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
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
GAP for this task?

Any help is appreciated. Thank you in advance. 

P.S. Any advices about algorithm are greatly appreciated. 
Best Regards, Serge.
mailto:teron at udm.ru
ICQ 315293596
Новые тарифные планы НИ - радикальное снижение цен
Новая услуга - Ночной дозор

More information about the Forum mailing list