Opened 6 years ago

Last modified 6 years ago

#18992 closed defect

Automaton.determinisation: do not ignore leading epsilon transitions — at Version 1

Reported by: cheuberg Owned by:
Priority: major Milestone: sage-6.9
Component: finite state machines Keywords:
Cc: skropf, dkrenn Merged in:
Authors: Clemens Heuberger Reviewers:
Report Upstream: N/A Work issues:
Branch: u/cheuberg/fsm/determinisation-ignored-initial-epsilon-transitions (Commits, GitHub, GitLab) Commit: 795cf2c09c626bf29ff4942b14f34ee90eb8eecd
Dependencies: Stopgaps:

Status badges

Description (last modified by cheuberg)

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.

Change History (1)

comment:1 Changed 6 years ago by cheuberg

  • Authors set to Clemens Heuberger
  • Branch set to u/cheuberg/fsm/determinisation-ignored-initial-epsilon-transitions
  • Commit set to 795cf2c09c626bf29ff4942b14f34ee90eb8eecd
  • Description modified (diff)
  • Status changed from new to needs_review
  • Summary changed from Missing final state in Automaton.determinisation to Automaton.determinisation: do not ignore leading epsilon transitions

New commits:

795cf2cTrac #18992: Automaton.determinisation: initial leading epsilon transitions
Note: See TracTickets for help on using tickets.