[GAP Forum] Question about semigroup and finite-state machine
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
Новые тарифные планы НИ - радикальное снижение цен
Новая услуга - Ночной дозор
More information about the Forum