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 )
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
comment:1 Changed 6 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 6 years ago by
comment:3 Changed 6 years ago by
Changed 6 years ago by
comment:4 Changed 6 years ago by
- Description modified (diff)
Changed 6 years ago by
comment:5 Changed 6 years ago by
- 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
- Description modified (diff)
comment:7 Changed 6 years ago by
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
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
comment:9 Changed 6 years ago by
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
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
- Cc eviatarbach added
comment:12 Changed 6 years ago by
for the bot : apply only trac_15078_fsm_automata_transducers.2.patch
comment:13 Changed 6 years ago by
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!
Changed 6 years ago by
comment:14 Changed 6 years ago by
- Description modified (diff)
comment:15 Changed 6 years ago by
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:
- conditional_iterator is ifilter in the module itertools
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 ofFSMstate
andFSMtransition
[...]
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)
ofFiniteStateMachine
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 anNotImplementedError
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.
Changed 6 years ago by
comment:16 Changed 6 years ago by
- Description modified (diff)
The patch does not change anything (except one index.rst and one all.py) in the existing Sage library; please review.