#18992: Automaton.determinisation: do not ignore leading epsilon transitions
-------------------------------------+-------------------------------------
Reporter: cheuberg | Owner:
Type: defect | Status: needs_review
Priority: major | Milestone: sage-6.9
Component: finite state | Resolution:
machines | Merged in:
Keywords: | Reviewers:
Authors: Clemens Heuberger | Work issues:
Report Upstream: N/A | Commit:
Branch: u/cheuberg/fsm | 795cf2c09c626bf29ff4942b14f34ee90eb8eecd
/determinisation-ignored-initial- | Stopgaps:
epsilon-transitions |
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by {'newvalue': u'Clemens Heuberger', 'oldvalue': ''}):
* status: new => needs_review
* author: => Clemens Heuberger
* branch: => u/cheuberg/fsm/determinisation-ignored-initial-epsilon-
transitions
* commit: => 795cf2c09c626bf29ff4942b14f34ee90eb8eecd
Old description:
> 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()
> []
> }}}
New description:
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.
--
Comment:
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=795cf2c09c626bf29ff4942b14f34ee90eb8eecd
795cf2c]||{{{Trac #18992: Automaton.determinisation: initial leading
epsilon transitions}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/18992#comment:1>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
