[GAP Forum] (no subject)

[Stephen Linton]

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 at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum