[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