Opened 4 years ago

Closed 3 years ago

#18992 closed defect (fixed)

Automaton.determinisation: do not ignore leading epsilon transitions

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: Daniel Krenn
Report Upstream: N/A Work issues:
Branch: 795cf2c (Commits) Commit: 795cf2c09c626bf29ff4942b14f34ee90eb8eecd
Dependencies: Stopgaps:

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 (3)

comment:1 Changed 4 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

comment:2 Changed 3 years ago by dkrenn

  • Reviewers set to Daniel Krenn
  • Status changed from needs_review to positive_review

Looks good.

comment:3 Changed 3 years ago by vbraun

  • Branch changed from u/cheuberg/fsm/determinisation-ignored-initial-epsilon-transitions to 795cf2c09c626bf29ff4942b14f34ee90eb8eecd
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.