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 )
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
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)
The patch does not change anything (except one index.rst and one all.py) in the existing Sage library; please review.