[GAP Forum] mistake with Union
Manuel Delgado
mdelgado at fc.up.pt
Wed Feb 27 18:59:15 GMT 2013
Dear Nikolai,
As the results in your message are those that I would expect, I am
perhaps missing something. If this is the case, please let me know.
Unless I am mistaken, the "union" produces and displays the correct
result. Note that
gap> [1..3]=[1,2,3];
true
Assuming that the function MinimalizedAut works correctly, the automata
rb1 and ddrb1 are equivalent:
gap>
rb1=Automaton("nondet",4,2,[[[2],[],[1,3],[4]],[[3],[1],[],[2,4]]],[1,3],[1]);;
gap> min := MinimalizedAut(rb1);
< deterministic automaton on 2 letters with 4 states >
gap> Display(min);
| 1 2 3 4
-----------------
a | 2 4 3 4
b | 3 1 3 2
Initial state: [ 2 ]
Accepting states: [ 2, 4 ]
gap>
gap> ddrb1 := NFAtoDFA(rb1);
< deterministic automaton on 2 letters with 5 states >
gap> mind := MinimalizedAut(ddrb1);
< deterministic automaton on 2 letters with 4 states >
gap> Display(mind);
| 1 2 3 4
-----------------
a | 2 4 3 4
b | 3 1 3 2
Initial state: [ 2 ]
Accepting states: [ 2, 4 ]
gap>
The way the deterministic automaton is computed from the non
deterministic one is perhaps different from the one you would expect,
but, as far as I can remember, it is exactly as described in the
automata package manual (which refers the power set construction and
points to a report easily obtainable from the internet.)
Hope this helps.
Best,
Manuel Delgado
On 02/27/2013 01:55 PM, NIK NIK wrote:
> Dear forum
>
> I 've find mistake with Union.
> ++++++++++++++++++++++++++++++++++++++++++++++
> gap> r := [ [ 2 ], [ ], [ 1, 3 ], [ 4 ] ];
> [ [ 2 ], [ ], [ 1, 3 ], [ 4 ] ]
> gap> Union( r{[]} );
> [ ]
> gap>st:= Union( r{[1,3]} );
> [ 1 .. 3 ]
> ++++++++++++++++++++++++++++++++++++++++++++++
>
> But I need the all elements in list st:=[1,2,3].
>
> This mistake makes many troubles in package "Automata".
> ++++++++++++++++++++++++++++++++++++++++++++++
> gap> Display(rb1);
> | 1 2 3 4
> -----------------------------------------
> a | [ 2 ] [ 1, 3 ] [ 4 ]
> b | [ 3 ] [ 1 ] [ 2, 4 ]
> Initial states: [ 1, 3 ]
> Accepting state: [ 1 ]
> gap> ddrb1:=NFAtoDFA(rb1);
> #I Determinized 4 to 5
> < deterministic automaton on 2 letters with 5 states >
> gap> Display(ddrb1);
> | 1 2 3 4 5
> --------------------
> a | 2 2 1 2 5
> b | 3 4 5 3 5
> Initial state: [ 1 ]
> Accepting states: [ 1, 2, 4 ]
> +++++++++++++++++++++++++++++++++++++++++++++++
>
>
> Thank you.
> Nikolai Krainyukov
>
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
More information about the Forum
mailing list