Dear Nikolay,
I don't think the automata package is actually wrong here, although it is,
perhaps
not being as clever as it could be.
The rather long regular expression you get from the non-deterministic automaton
still describes the same language
as (aUb)*, albeit in a rather clumsy way.
Steve
On 9 Mar 2011, at 13:18, NIK NIK wrote:
> Dear GAP Forum:
>
> I work with “Automata” package and find interesting thing:
>
> gap> ab_star:=RationalExpression("(aUb)*");
> (aUb)*
>
> gap> aut_star:=RatExpToNDAut( ab_star );
> < non deterministic automaton on 2 letters with 3 states >
> gap> Display(aut_star);
> | 1 2 3
> ---------------------------
> a | [ 1 ] [ 1 ] [ 1 ]
> b | [ 2 ] [ 2 ] [ 2 ]
> Initial state: [ 3 ]
> Accepting states: [ 1, 2, 3 ]
>
> gap> daut_star:=RatExpToAut( ab_star );
> < deterministic automaton on 2 letters with 1 states >
> gap> Display(daut_star);
> | 1
> --------
> a | 1
> b | 1
> Initial state: [ 1 ]
> Accepting state: [ 1 ]
>
> gap> r_aut_star:=AutomatonToRatExp ( aut_star );
> (aa*bUb)(aa*bUb)*(aa*U@)Uaa*U@
> gap> r_daut_star:=AutomatonToRatExp ( daut_star );
> (aUb)*
>
>
> Is something wrong with regular expression for nondet automaton?
>
> Could someone please point out where the error is?
>
>
> Sincerely,
> Nikolay Krayinyukov
>
> _______________________________________________
> Forum mailing list
> Forum@mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
_______________________________________________
Forum mailing list
Forum@mail.gap-system.org
http://mail.gap-system.org/mailman/listinfo/forum
