Opened 6 years ago

Last modified 3 years ago

#15078 closed enhancement

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

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.4.patch

Change History (21)

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)

comment:15 Changed 6 years ago by dkrenn

I've uploaded a new patch: http://trac.sagemath.org/attachment/ticket/15078/trac_15078_fsm_automata_transducers.3.patch It is already rebased to 5.12

Replying to chapoton:

Here is the report of pyflakes [...] This needs to be cleaned

Done.

Replying to vdelecroix:

Changed.

  • you should use Word and Words (in sage.combinat.words)

See #15267 together with comments below.

Replying to vbraun:

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

Done.

Are you sure you need FSMProcessIterator in the global namespace? Similarly, instead of FSMstate and FSMtransition [...]

Those things are now local. Only FiniteStateMachine, Automaton and Transducer are now global.

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

This is now #15266 (which can be solved after #15264). See also the discussion "Mutability" on sage-devel ​https://groups.google.com/forum/#!topic/sage-devel/dnXSgh56Boo

Replying to slabbe:

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.

This is now #15267.

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/

I thought I followed those rules. Anyhow, I found some misplaced spaces and non-spaces. Now changed (and hopefully nothing missed).

Replying to slabbe:

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', [])

No, I would not raise a NotImplementedError, since it isn't one, but just one possible outcome is given. But I agree that it could be a problem. Therefore I added a comment in the documentation of process.

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.

I cannot reproduce this behaviour. Anyhow, I added the example above as a doctest.

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

Changed 6 years ago by dkrenn

comment:16 Changed 6 years ago by dkrenn

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