#15078: new module: finite state machines, automata, transducers
-------------------------------------------------+-------------------------
Reporter: dkrenn | Owner:
Type: enhancement | Status:
Priority: major | needs_review
Component: combinatorics | Milestone: sage-5.13
Keywords: finite state machines, | Resolution:
automaton, transducer | Merged in:
Authors: Clemens Heuberger, Daniel | Reviewers:
Krenn, Sara Kropf | Work issues:
Report Upstream: N/A | Commit:
Branch: | Stopgaps:
Dependencies: |
-------------------------------------------------+-------------------------
Comment (by slabbe):
I did a more careful reading of the patch today. All tests passed (5.59s
for
552 tests which is quite efficient). Coverage is 100% (115 of 115).
Documentation builds fine without warnings.
I am ready to give a positive review to the patch provided the following
three
more things are fixed.
1.
In the file `doc/en/reference/combinat/index.rst`, the finite state
module is at the very end of the list after Miscellaneous and
Combinatorial
maps. I suggest that you put it before the Words section instead.
2.
The documentation for the `data` input of `FiniteStateMachine` is not
properly documented. It is not usual to see such pseudo code examples and
they
are not easy to read, thus not very usefull (personnaly, my eyes do not
want to
look at them).
{{{
- ``data`` -- can be any of the following:
- ``{A:{B:{word_in=0, word_out=1}, C:{word_in=1, word_out=1}, ...}``
- ``{A:{B:(0, 1), C:(1, 1), ...}``
- ``{A:{B:FSMTransition(A, B, 0, 1), C:FSMTransition(A, C, 1, 1),
...}``
- ``{A:[(B, 0, 1), (C, 1, 1)], ...}``
- ``{A:[FSMTransition(A, B, 0, 1), FSMTransition(A, C, 1, 1)],
...}``
- ``[{from_state:A, to_state:B, word_in:0, word_out:1}, \
from_state:A, to_state:C, word_in:1, word_out:1}, ...]``
- ``[(A, B, 0, 1), (A, C, 1, 1), ...]``
- ``[FSMTransition(A, B, 0, 1), FSMTransition(A, C, 1, 1), ...]``
}}}
I suggest that you follow the documentation of `Graph` which
is now quite good. See:
{{{
sage: Graph?
}}}
You will see that the possible cases of data for `Graph`
are listed verbosely with english words with empty line in between them.
The
list is numeroted with numbers. And the same numbers are used below in the
examples section where many examples are provided for *each* case.
3.
Make three classes for `FiniteStateMachine`, `Automaton` and `Transducer`.
Indeed, `FiniteStateMachine` has 77 methods. Of those only 7 of them
depends
on the `mode` attribute. I have copied below the relevant part of the code
where the `mode` attribute is used in those six methods:
{{{
#!python
class FiniteStateMachine(SageObject):
def __init__(self, ..., mode=None, ...):
...
self.mode = mode
...
def empty_copy(self, memo=None):
...
new.mode = deepcopy(self.mode, memo)
...
def _latex_(self):
...
if self.mode == 'automaton':
labels.append(format_transition_label(
transition.word_in))
else:
labels.append(format_transition_label(
transition.word_in) + "\\mid" + \
format_transition_label(transition.word_out))
...
def projection(self, what='input'):
new = self.empty_copy()
new.mode='automaton'
...
def determinisation(self):
assert self.mode == 'automaton'
...
def minimization(self, algorithm=None):
if self.mode is None:
raise NotImplementedError, "The mode attribute must be set."
if self.mode == 'transducer':
raise NotImplementedError, "Minimization for Transducer is not
implemented. Try the simplification method."
if not self.mode == 'automaton':
raise NotImplementedError
...
def simplification(self):
if self.mode != 'transducer':
raise NotImplementedError, "Simplification is only implemented
for Transducers. For Automata, use minimization instead"
...
}}}
I would leave the 70 methods not mentioned above in the class
`FiniteStateMachine`. Then, according to how each of the 7 methods are
used,
I would do the following for each of them:
- `__init__`: This method can be kept as it is in the
`FiniteStateMachine`
class and I believe the line `self.mode = mode` can just be deleted.
- `empty_copy`: This method can be kept in the `FiniteStateMachine` and I
believe the line `new.mode = 'automaton'` can just be deleted.
- `_latex_`: This method can be kept in the `FiniteStateMachine` and I
would move the code depending on the mode inside a method in the
classes
`Automaton` and `Transducer`. This method could be called
`_transition_label` or something like that would return the label of a
transition in the according way. Maybe this method will just ask the
transition to do it.
- `projection`: This method can be kept in the `FiniteStateMachine` and
could return an instance of an Automaton.
- `determinisation` and `minimization` : I would put these methods in the
class `Automaton`
- `simplification` : I would put this method in the class `Transducer`
Finally, I would replace the following functions::
{{{
#!python
def Transducer(*args, **kwargs):
...
def Automaton(*args, **kwargs):
...
}}}
by classes with the same docstrings in the following way (the constructor
is
stil the same actually defined for `FiniteStateMachine`)::
{{{
#!python
class Transducer(FiniteStateMachine):
r"""
same doctrings here as for def Transducer
"""
def _transition_label(self, some_args):
r"""
Return the proper transition label.
Method used by ``_latex_`` method
"""
...
def simplification(self):
...
class Automaton(FiniteStateMachine):
r"""
same doctrings here as for def Automaton
"""
def _transition_label(self, some_args):
r"""
Return the proper transition label.
Method used by ``_latex_`` method
"""
...
def determinisation(self):
...
def minimization(self):
...
}}}
Cheers!
Sébastien
--
Ticket URL: <http://trac.sagemath.org/ticket/15078#comment:20>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
