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.

Sign up for GitHub

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

Jump to bottom

Automaton.determinisation: do not ignore leading epsilon transitions #18992

Closed
cheuberg opened this issue Aug 5, 2015 · 8 comments
Closed

Automaton.determinisation: do not ignore leading epsilon transitions #18992

cheuberg opened this issue Aug 5, 2015 · 8 comments
Labels
c: finite state machines p: major / 3 t: bug
Milestone
sage-6.9

Comments

@cheuberg
Copy link
Contributor

cheuberg commented Aug 5, 2015

After determinisation, the automaton may have no final state:

sage: A = Automaton([(0, 1, []), (1, 1, 0)], initial_states=[0], final_states=[1])
sage: A.transitions()
[Transition from 0 to 1: -|-, Transition from 1 to 1: 0|-]
sage: A.final_states()
[1]
sage: B = A.determinisation().relabeled()
sage: B.initial_states()
[0]
sage: B.final_states()
[]

This is because leading epsilon transitions had been ignored.

CC: @sagetrac-skropf @dkrenn

Component: finite state machines

Author: Clemens Heuberger

Branch/Commit: 795cf2c

Reviewer: Daniel Krenn

Issue created by migration from https://trac.sagemath.org/ticket/18992
@cheuberg cheuberg added this to the sage-6.9 milestone Aug 5, 2015
@cheuberg
Copy link
Contributor Author

cheuberg commented Aug 5, 2015

Branch: u/cheuberg/fsm/determinisation-ignored-initial-epsilon-transitions

@cheuberg
Copy link
Contributor Author

cheuberg commented Aug 5, 2015

New commits:

795cf2cTrac #18992: Automaton.determinisation: initial leading epsilon transitions

@cheuberg

This comment has been minimized.

Sign in to view
@cheuberg
Copy link
Contributor Author

cheuberg commented Aug 5, 2015

Commit: 795cf2c

@cheuberg
Copy link
Contributor Author

cheuberg commented Aug 5, 2015

Author: Clemens Heuberger

@cheuberg cheuberg changed the title Missing final state in Automaton.determinisation Automaton.determinisation: do not ignore leading epsilon transitions Aug 5, 2015
@dkrenn
Copy link
Contributor

dkrenn commented Sep 8, 2015

Reviewer: Daniel Krenn

@dkrenn
Copy link
Contributor

dkrenn commented Sep 8, 2015

comment:2

Looks good.

@vbraun
Copy link
Member

vbraun commented Sep 9, 2015

Changed branch from u/cheuberg/fsm/determinisation-ignored-initial-epsilon-transitions to 795cf2c

@vbraun vbraun closed this as completed in c3c139f Sep 9, 2015
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
c: finite state machines p: major / 3 t: bug
Projects
None yet
Milestone
sage-6.9
Development

No branches or pull requests
3 participants
@vbraun @cheuberg @dkrenn