sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.35k stars 462 forks source link

Failed to find kleene star of a finite automaton #22858

Open f5181210-fdb3-4942-b604-53921e658f47 opened 7 years ago

f5181210-fdb3-4942-b604-53921e658f47 commented 7 years ago

Given the following automaton

aut = Automaton({'p':[('p','b'),('q','a')], 'q':[('r','a'), ('r','b')], 'r':[('p','a'),('p','b')]}, initial_states=['p'], final_states=['r'])

and its kleene star

_kleene = Automaton({'i':[('p','b'),('q','a')], 'p':[('p','b'),('q','a')], 'q':[('r','a'), ('r','b'), ('i','a'), ('i','b')], 'r':[('p','a'),('p','b')]}, initial_states=['i'], final_states=['i'])

the following code

_kleene.is_equivalent(aut.kleene_star())

outputs False, which it shouldn't. The automaton produced by aut.kleene_star() differs from aut only in that p becomes also final state.

Component: combinatorics

Keywords: finite state machines, automata, kleene star

Issue created by migration from https://trac.sagemath.org/ticket/22858

f5181210-fdb3-4942-b604-53921e658f47 commented 7 years ago

Description changed:

--- 
+++ 
@@ -13,5 +13,5 @@

_kleene.is_equivalent(aut.kleene_star())

-outputs False, which it shouldn't. The automaton produced by `aut.kleene_star()` differs from `aut` only in that the input state becomes also final state.
+outputs False, which it shouldn't. The automaton produced by `aut.kleene_star()` differs from `aut` only in that `p` becomes also final state.