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 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:[EMAIL PROTECTED] ICQ 315293596 ---------------------------------------------------- Новые тарифные планы НИ - радикальное снижение цен Новая услуга - Ночной дозор http://www.mark-itt.ru/MARK-ITT/Contract/current/price.htm _______________________________________________ Forum mailing list [email protected] http://mail.gap-system.org/mailman/listinfo/forum
