Opened 6 years ago

Last modified 3 years ago

#15078 closed enhancement

new module: finite state machines, automata, transducers — at Version 14

Reported by: dkrenn Owned by:
Priority: major Milestone: sage-5.13
Component: combinatorics Keywords: finite state machines, automaton, transducer
Cc: eviatarbach, tmonteil, cheuberg Merged in:
Authors: Clemens Heuberger, Daniel Krenn, Sara Kropf Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by dkrenn)

This module adds a class for

  • finite state machine,
  • finite automaton,
  • finite transducer.

Apply only trac_15078_fsm_automata_transducers.3.patch

Change History (18)

Changed 6 years ago by dkrenn

comment:1 Changed 6 years ago by dkrenn

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 6 years ago by dkrenn

The patch does not change anything (except one index.rst and one all.py) in the existing Sage library; please review.

comment:3 Changed 6 years ago by dkrenn

  • Authors set to Clemens Heuberger, Daniel Krenn, Sara Kropf

Changed 6 years ago by dkrenn

comment:4 Changed 6 years ago by dkrenn

  • Description modified (diff)

Changed 6 years ago by dkrenn

comment:5 Changed 6 years ago by dkrenn

  • Description modified (diff)

Another change in the docstrings, all changes are now in trac_15078_fsm_automata_transducers.2.patch

comment:6 Changed 6 years ago by dkrenn

  • Description modified (diff)

comment:7 Changed 6 years ago by chapoton

Here is the report of pyflakes

sage/combinat/finite_state_machine.py:293: 'SR' imported but unused sage/combinat/finite_state_machine.py:1074: local variable 'from_state' is assigned to but never used sage/combinat/finite_state_machine.py:1077: local variable 'to_state' is assigned to but never used sage/combinat/finite_state_machine.py:1160: redefinition of unused 'itertools' from line 304 sage/combinat/finite_state_machine.py:2213: local variable 'to_state' is assigned to but never used sage/combinat/finite_state_machine.py:3372: local variable 'new_transition' is assigned to but never used

This needs to be cleaned

comment:8 Changed 6 years ago by vdelecroix

Hi all,

Right now I just have a quick look but

  • the lot of examples at the begining are very nice!
  • conditional_iterator is ifilter in the module itertools
  • you should use Word and Words (in sage.combinat.words)

Vincent

Last edited 6 years ago by vdelecroix (previous) (diff)

comment:9 Changed 6 years ago by vbraun

INPUT/OUTPUT needs to be documented in every method (see developer manual)

Are you sure you need FSMProcessIterator in the global namespace? Similarly, instead of FSMstate and FSMtransition, which are useless by themselves, just do

    sage: fsm = FiniteStateMachine() 
    sage: day = fsm.add_state('day')
    sage: night = fsm.add_state('night')
    sage: sunrise = fsm.add_transition(night, day)

in addition to

    sage: sunrise = fsm.add_transition('night', 'day')

Also, instead of reinventing the mutability wheel there is sage.structure.mutability.Mutability to inherit from.

comment:10 Changed 6 years ago by slabbe

Nice! I was needing such a class for a while! I don't know if you should really use sage.combinat.words stuff in your code, maybe in a method def language(self, n) of FiniteStateMachine that would return an iterator over all words of length n recognized by the automaton. Anyhow, sage.combinat.words will definitively benefits from it, for instance for representing automatic sequences.

I agree with both comments of vbraun above. The code is well written. Only small fixes must be done like adding INPUT and OUPUT blocks and follow Python convention of having one space before and after = character (except for arguments of a function). See PEP 8 at http://www.python.org/dev/peps/pep-0008/

comment:11 Changed 6 years ago by eviatarbach

  • Cc eviatarbach added

comment:12 Changed 6 years ago by chapoton

for the bot : apply only trac_15078_fsm_automata_transducers.2.patch

comment:13 Changed 6 years ago by slabbe

I did some small tests yesterday. Below are few of them.

In the following example, the output of process should be True, but it returns False. Should the process method raise an NotImplementedError if the automaton is not deterministic?::

    sage: D = {'A': [('A', 'a'), ('B', 'a'), ('A', 'b')], 'C': [], 'B': [('C', 'b')]}
    sage: auto = Automaton(D, initial_states=['A'], final_states=['C'])
    sage: auto.is_deterministic()
    False
    sage: auto.process(list('aaab'))
    (False, State 'A', [])

The determinisation is broken for this automaton. Why?::

    sage: auto.states()
    [State 'A', State 'B', State 'C']
    sage: auto.determinisation()
    ...
    LookupError: No state with label State 'A' found.

Apparently, label needs to be integers for determinisation to work? ::

    sage: L = [('A', 'A', 0), ('A', 'B', 0), ('A','A',1), ('B','C', 1)]
    sage: auto = Automaton(L, initial_states=['A'], final_states=['C'])
    sage: auto.process([0, 0, 0, 1])
    (False, State 'A', [])
    sage: auto.determinisation()
    finite state machine with 3 states
    sage: auto.determinisation().states()
    [State frozenset(['A']), State frozenset(['A', 'B']), State frozenset(['A', 'C'])]

Cheers!

Last edited 6 years ago by slabbe (previous) (diff)

Changed 6 years ago by dkrenn

comment:14 Changed 6 years ago by dkrenn

  • Description modified (diff)
Note: See TracTickets for help on using tickets.