Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Failed to find kleene star of a finite automaton #22858

Open
sagetrac-mirgee mannequin opened this issue Apr 22, 2017 · 1 comment
Open

Failed to find kleene star of a finite automaton #22858

sagetrac-mirgee mannequin opened this issue Apr 22, 2017 · 1 comment

Comments

@sagetrac-mirgee
Copy link
Mannequin

sagetrac-mirgee mannequin commented Apr 22, 2017

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

@sagetrac-mirgee sagetrac-mirgee mannequin added this to the sage-8.0 milestone Apr 22, 2017
@sagetrac-mirgee

This comment has been minimized.

@mkoeppe mkoeppe removed this from the sage-8.0 milestone Dec 29, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant