#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 dkrenn):
I've uploaded a new patch:
http://trac.sagemath.org/attachment/ticket/15078/trac_15078_fsm_automata_transducers.3.patch
Replying to [comment:7 chapoton]:
> Here is the report of `pyflakes` [...]
> This needs to be cleaned
Done.
Replying to [comment:8 vdelecroix]:
> - conditional_iterator is ifilter in the module
[http://docs.python.org/2/library/itertools.html itertools]
Changed.
> - you should use Word and Words (in sage.combinat.words)
See #15267 together with comments below.
Replying to [comment:9 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 [comment:10 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 [comment:13 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.
--
Ticket URL: <http://trac.sagemath.org/ticket/15078#comment:15>
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.
