Sage: Ticket #15078: new module: finite state machines, automata, transducers
https://trac.sagemath.org/ticket/15078
<p>
This module adds a class for
</p>
<ul><li>finite state machine,
</li><li>finite automaton,
</li><li>finite transducer.
</li></ul><p>
Apply only <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/15078/trac_15078_fsm_automata_transducers.8.patch" title="Attachment 'trac_15078_fsm_automata_transducers.8.patch' in Ticket #15078">trac_15078_fsm_automata_transducers.8.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/15078/trac_15078_fsm_automata_transducers.8.patch" title="Download"></a>
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/15078
Trac 1.1.6dkrennThu, 22 Aug 2013 12:38:25 GMTattachment set
https://trac.sagemath.org/ticket/15078
https://trac.sagemath.org/ticket/15078
<ul>
<li><strong>attachment</strong>
set to <em>trac_15078_fsm_automata_transducers.patch</em>
</li>
</ul>
TicketdkrennThu, 22 Aug 2013 12:39:46 GMTstatus, description changed
https://trac.sagemath.org/ticket/15078#comment:1
https://trac.sagemath.org/ticket/15078#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/15078?action=diff&version=1">diff</a>)
</li>
</ul>
TicketdkrennThu, 22 Aug 2013 12:42:04 GMT
https://trac.sagemath.org/ticket/15078#comment:2
https://trac.sagemath.org/ticket/15078#comment:2
<p>
The patch does not change anything (except one index.rst and one all.py) in the existing Sage library; please review.
</p>
TicketdkrennThu, 22 Aug 2013 13:42:55 GMTauthor set
https://trac.sagemath.org/ticket/15078#comment:3
https://trac.sagemath.org/ticket/15078#comment:3
<ul>
<li><strong>author</strong>
set to <em>Clemens Heuberger, Daniel Krenn, Sara Kropf</em>
</li>
</ul>
TicketdkrennThu, 22 Aug 2013 18:07:19 GMTattachment set
https://trac.sagemath.org/ticket/15078
https://trac.sagemath.org/ticket/15078
<ul>
<li><strong>attachment</strong>
set to <em>trac_15078_fsm_docstrings.patch</em>
</li>
</ul>
TicketdkrennThu, 22 Aug 2013 18:08:03 GMTdescription changed
https://trac.sagemath.org/ticket/15078#comment:4
https://trac.sagemath.org/ticket/15078#comment:4
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/15078?action=diff&version=4">diff</a>)
</li>
</ul>
TicketdkrennTue, 03 Sep 2013 08:21:31 GMTattachment set
https://trac.sagemath.org/ticket/15078
https://trac.sagemath.org/ticket/15078
<ul>
<li><strong>attachment</strong>
set to <em>trac_15078_fsm_automata_transducers.2.patch</em>
</li>
</ul>
TicketdkrennTue, 03 Sep 2013 08:23:59 GMTdescription changed
https://trac.sagemath.org/ticket/15078#comment:5
https://trac.sagemath.org/ticket/15078#comment:5
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/15078?action=diff&version=5">diff</a>)
</li>
</ul>
<p>
Another change in the docstrings, all changes are now in trac_15078_fsm_automata_transducers.2.patch
</p>
TicketdkrennTue, 03 Sep 2013 08:36:59 GMTdescription changed
https://trac.sagemath.org/ticket/15078#comment:6
https://trac.sagemath.org/ticket/15078#comment:6
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/15078?action=diff&version=6">diff</a>)
</li>
</ul>
TicketchapotonThu, 12 Sep 2013 13:02:35 GMT
https://trac.sagemath.org/ticket/15078#comment:7
https://trac.sagemath.org/ticket/15078#comment:7
<p>
Here is the report of <code>pyflakes</code>
</p>
<p>
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
</p>
<p>
This needs to be cleaned
</p>
TicketvdelecroixThu, 12 Sep 2013 13:15:24 GMT
https://trac.sagemath.org/ticket/15078#comment:8
https://trac.sagemath.org/ticket/15078#comment:8
<p>
Hi all,
</p>
<p>
Right now I just have a quick look but
</p>
<ul><li>the lot of examples at the begining are very nice!
</li><li>conditional_iterator is ifilter in the module <a class="ext-link" href="http://docs.python.org/2/library/itertools.html"><span class="icon"></span>itertools</a>
</li><li>you should use Word and Words (in sage.combinat.words)
</li></ul><p>
Vincent
</p>
TicketvbraunThu, 12 Sep 2013 14:23:28 GMT
https://trac.sagemath.org/ticket/15078#comment:9
https://trac.sagemath.org/ticket/15078#comment:9
<p>
INPUT/OUTPUT needs to be documented in every method (see developer manual)
</p>
<p>
Are you sure you need <code>FSMProcessIterator</code> in the global namespace? Similarly, instead of <code>FSMstate</code> and <code>FSMtransition</code>, which are useless by themselves, just do
</p>
<pre class="wiki"> sage: fsm = FiniteStateMachine()
sage: day = fsm.add_state('day')
sage: night = fsm.add_state('night')
sage: sunrise = fsm.add_transition(night, day)
</pre><p>
in addition to
</p>
<pre class="wiki"> sage: sunrise = fsm.add_transition('night', 'day')
</pre><p>
Also, instead of reinventing the mutability wheel there is <code>sage.structure.mutability.Mutability</code> to inherit from.
</p>
TicketslabbeThu, 12 Sep 2013 15:19:19 GMT
https://trac.sagemath.org/ticket/15078#comment:10
https://trac.sagemath.org/ticket/15078#comment:10
<p>
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 <code>def language(self, n)</code> of <code>FiniteStateMachine</code> 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.
</p>
<p>
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 <code>=</code> character (except for arguments of a function). See PEP 8 at <a class="ext-link" href="http://www.python.org/dev/peps/pep-0008/"><span class="icon"></span>http://www.python.org/dev/peps/pep-0008/</a>
</p>
TicketeviatarbachSun, 15 Sep 2013 03:37:30 GMTcc set
https://trac.sagemath.org/ticket/15078#comment:11
https://trac.sagemath.org/ticket/15078#comment:11
<ul>
<li><strong>cc</strong>
<em>eviatarbach</em> added
</li>
</ul>
TicketchapotonSun, 15 Sep 2013 18:51:46 GMT
https://trac.sagemath.org/ticket/15078#comment:12
https://trac.sagemath.org/ticket/15078#comment:12
<p>
for the bot : apply only trac_15078_fsm_automata_transducers.2.patch
</p>
TicketslabbeWed, 02 Oct 2013 09:03:39 GMT
https://trac.sagemath.org/ticket/15078#comment:13
https://trac.sagemath.org/ticket/15078#comment:13
<p>
I did some small tests yesterday. Below are few of them.
</p>
<p>
In the following example, the output of process should be True, but it returns False. Should the <code>process</code> method raise an <code>NotImplementedError</code> if the automaton is not deterministic?::
</p>
<pre class="wiki"> 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', [])
</pre><p>
The determinisation is broken for this automaton. Why?::
</p>
<pre class="wiki"> sage: auto.states()
[State 'A', State 'B', State 'C']
sage: auto.determinisation()
...
LookupError: No state with label State 'A' found.
</pre><p>
Apparently, label needs to be integers for determinisation to work? ::
</p>
<pre class="wiki"> 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'])]
</pre><p>
Cheers!
</p>
TicketdkrennWed, 09 Oct 2013 11:43:13 GMTattachment set
https://trac.sagemath.org/ticket/15078
https://trac.sagemath.org/ticket/15078
<ul>
<li><strong>attachment</strong>
set to <em>trac_15078_fsm_automata_transducers.3.patch</em>
</li>
</ul>
TicketdkrennWed, 09 Oct 2013 11:44:03 GMTdescription changed
https://trac.sagemath.org/ticket/15078#comment:14
https://trac.sagemath.org/ticket/15078#comment:14
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/15078?action=diff&version=14">diff</a>)
</li>
</ul>
TicketdkrennWed, 09 Oct 2013 12:00:57 GMT
https://trac.sagemath.org/ticket/15078#comment:15
https://trac.sagemath.org/ticket/15078#comment:15
<p>
I've uploaded a new patch: <a class="ext-link" href="http://trac.sagemath.org/attachment/ticket/15078/trac_15078_fsm_automata_transducers.3.patch"><span class="icon"></span>http://trac.sagemath.org/attachment/ticket/15078/trac_15078_fsm_automata_transducers.3.patch</a>
It is already rebased to 5.12
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15078#comment:7" title="Comment 7">chapoton</a>:
</p>
<blockquote class="citation">
<p>
Here is the report of <code>pyflakes</code> [...]
This needs to be cleaned
</p>
</blockquote>
<p>
Done.
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15078#comment:8" title="Comment 8">vdelecroix</a>:
</p>
<blockquote class="citation">
<ul><li>conditional_iterator is ifilter in the module <a class="ext-link" href="http://docs.python.org/2/library/itertools.html"><span class="icon"></span>itertools</a>
</li></ul></blockquote>
<p>
Changed.
</p>
<blockquote class="citation">
<ul><li>you should use Word and Words (in sage.combinat.words)
</li></ul></blockquote>
<p>
See <a class="closed ticket" href="https://trac.sagemath.org/ticket/15267" title="enhancement: automaton: iterator over words of language (closed: fixed)">#15267</a> together with comments below.
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15078#comment:9" title="Comment 9">vbraun</a>:
</p>
<blockquote class="citation">
<p>
INPUT/OUTPUT needs to be documented in every method (see developer manual)
</p>
</blockquote>
<p>
Done.
</p>
<blockquote class="citation">
<p>
Are you sure you need <code>FSMProcessIterator</code> in the global namespace? Similarly, instead of <code>FSMstate</code> and <code>FSMtransition</code> [...]
</p>
</blockquote>
<p>
Those things are now local. Only <code>FiniteStateMachine</code>, <code>Automaton</code> and <code>Transducer</code> are now global.
</p>
<blockquote class="citation">
<p>
Also, instead of reinventing the mutability wheel there is <code>sage.structure.mutability.Mutability</code> to inherit from.
</p>
</blockquote>
<p>
This is now <a class="new ticket" href="https://trac.sagemath.org/ticket/15266" title="defect: finite state machines: inherit from Mutability (new)">#15266</a> (which can be solved after <a class="new ticket" href="https://trac.sagemath.org/ticket/15264" title="defect: make Mutability class ready to be used (new)">#15264</a>). See also the discussion "Mutability" on sage-devel <a class="ext-link" href="https://groups.google.com/forum/#!topic/sage-devel/dnXSgh56Boo"><span class="icon"></span>https://groups.google.com/forum/#!topic/sage-devel/dnXSgh56Boo</a>
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15078#comment:10" title="Comment 10">slabbe</a>:
</p>
<blockquote class="citation">
<p>
I don't know if you should really use sage.combinat.words stuff in your code, maybe in a method <code>def language(self, n)</code> of <code>FiniteStateMachine</code> 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.
</p>
</blockquote>
<p>
This is now <a class="closed ticket" href="https://trac.sagemath.org/ticket/15267" title="enhancement: automaton: iterator over words of language (closed: fixed)">#15267</a>.
</p>
<blockquote class="citation">
<p>
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 <code>=</code> character (except for arguments of a function). See PEP 8 at <a class="ext-link" href="http://www.python.org/dev/peps/pep-0008/"><span class="icon"></span>http://www.python.org/dev/peps/pep-0008/</a>
</p>
</blockquote>
<p>
I thought I followed those rules. Anyhow, I found some misplaced spaces and non-spaces. Now changed (and hopefully nothing missed).
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15078#comment:13" title="Comment 13">slabbe</a>:
</p>
<blockquote class="citation">
<p>
In the following example, the output of process should be True, but it returns False. Should the <code>process</code> method raise an <code>NotImplementedError</code> if the automaton is not deterministic?::
</p>
<pre class="wiki"> 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', [])
</pre></blockquote>
<p>
No, I would not raise a <code>NotImplementedError</code>, 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 <code>process</code>.
</p>
<blockquote class="citation">
<p>
The determinisation is broken for this automaton. Why?::
</p>
<pre class="wiki"> sage: auto.states()
[State 'A', State 'B', State 'C']
sage: auto.determinisation()
...
LookupError: No state with label State 'A' found.
</pre></blockquote>
<p>
I cannot reproduce this behaviour. Anyhow, I added the example above as a doctest.
</p>
TicketdkrennMon, 04 Nov 2013 16:01:40 GMTattachment set
https://trac.sagemath.org/ticket/15078
https://trac.sagemath.org/ticket/15078
<ul>
<li><strong>attachment</strong>
set to <em>trac_15078_fsm_automata_transducers.4.patch</em>
</li>
</ul>
TicketdkrennMon, 04 Nov 2013 16:02:07 GMTdescription changed
https://trac.sagemath.org/ticket/15078#comment:16
https://trac.sagemath.org/ticket/15078#comment:16
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/15078?action=diff&version=16">diff</a>)
</li>
</ul>
TicketdkrennMon, 04 Nov 2013 16:05:42 GMT
https://trac.sagemath.org/ticket/15078#comment:17
https://trac.sagemath.org/ticket/15078#comment:17
<p>
There is a new version available: <a class="ext-link" href="http://trac.sagemath.org/attachment/ticket/15078/trac_15078_fsm_automata_transducers.4.patch"><span class="icon"></span>http://trac.sagemath.org/attachment/ticket/15078/trac_15078_fsm_automata_transducers.4.patch</a>
We fixed some small bugs, made the output of some functions more consistent, and improved the documentation.
</p>
<p>
We'd be happy if someone could review the patch.
</p>
TicketdkrennMon, 04 Nov 2013 17:27:44 GMTattachment set
https://trac.sagemath.org/ticket/15078
https://trac.sagemath.org/ticket/15078
<ul>
<li><strong>attachment</strong>
set to <em>trac_15078_fsm_automata_transducers.5.patch</em>
</li>
</ul>
TicketdkrennMon, 04 Nov 2013 17:29:05 GMTdescription changed
https://trac.sagemath.org/ticket/15078#comment:18
https://trac.sagemath.org/ticket/15078#comment:18
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/15078?action=diff&version=18">diff</a>)
</li>
</ul>
<p>
The module is now imported lazy. Updated patch is
<a class="ext-link" href="http://trac.sagemath.org/attachment/ticket/15078/trac_15078_fsm_automata_transducers.5.patch"><span class="icon"></span>http://trac.sagemath.org/attachment/ticket/15078/trac_15078_fsm_automata_transducers.5.patch</a>
</p>
TicketslabbeWed, 06 Nov 2013 12:31:44 GMT
https://trac.sagemath.org/ticket/15078#comment:19
https://trac.sagemath.org/ticket/15078#comment:19
<p>
I had a question concerning the choices you made for the classes. Why did you choose to have only one class <code>FiniteStateMachine</code> with the mode argument?
</p>
<div class="wiki-code"><div class="code"><pre><span class="k">def</span> <span class="nf">Automaton</span><span class="p">(</span><span class="o">*</span>args<span class="p">,</span> <span class="o">**</span>kwargs<span class="p">):</span>
<span class="k">return</span> FiniteStateMachine<span class="p">(</span>mode<span class="o">=</span><span class="s">'automaton'</span><span class="p">,</span> <span class="o">*</span>args<span class="p">,</span> <span class="o">**</span>kwargs<span class="p">)</span>
<span class="k">def</span> <span class="nf">Transducer</span><span class="p">(</span><span class="o">*</span>args<span class="p">,</span> <span class="o">**</span>kwargs<span class="p">):</span>
<span class="k">return</span> FiniteStateMachine<span class="p">(</span>mode<span class="o">=</span><span class="s">'transducer'</span><span class="p">,</span> <span class="o">*</span>args<span class="p">,</span> <span class="o">**</span>kwargs<span class="p">)</span>
</pre></div></div><p>
The role of this mode argument is usually done transparently by the classes.
Was it better than having three classes <code>class FiniteStateMachine(SageObject)</code>, <code>class Automaton(FiniteStateMachine)</code> and <code>class Transducer(FiniteStateMachine)</code> ? Another option closer to what you have done could be two classes : <code>class Transducer(SageObject)</code> and <code>class Automaton(Transducer)</code> ? All this depends on the way the methods are implemented and how much they depends on the class instance. What would be best do you think?
</p>
<p>
There is a Sage Afternoon today in Paris. I hope to have time to take a look more deeply at the most recent version of the patch.
</p>
TicketslabbeThu, 07 Nov 2013 23:25:17 GMT
https://trac.sagemath.org/ticket/15078#comment:20
https://trac.sagemath.org/ticket/15078#comment:20
<p>
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.
</p>
<p>
I am ready to give a positive review to the patch provided the following three
more things are fixed.
</p>
<ol><li>
</li></ol><p>
In the file <code>doc/en/reference/combinat/index.rst</code>, 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.
</p>
<p>
2.
</p>
<p>
The documentation for the <code>data</code> input of <code>FiniteStateMachine</code> 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).
</p>
<pre class="wiki"> - ``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), ...]``
</pre><p>
I suggest that you follow the documentation of <code>Graph</code> which
is now quite good. See:
</p>
<pre class="wiki">sage: Graph?
</pre><p>
You will see that the possible cases of data for <code>Graph</code>
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.
</p>
<p>
3.
</p>
<p>
Make three classes for <code>FiniteStateMachine</code>, <code>Automaton</code> and <code>Transducer</code>.
</p>
<p>
Indeed, <code>FiniteStateMachine</code> has 77 methods. Of those only 7 of them depends
on the <code>mode</code> attribute. I have copied below the relevant part of the code
where the <code>mode</code> attribute is used in those six methods:
</p>
<div class="wiki-code"><div class="code"><pre><span class="k">class</span> <span class="nc">FiniteStateMachine</span><span class="p">(</span>SageObject<span class="p">):</span>
<span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="o">...</span><span class="p">,</span> mode<span class="o">=</span><span class="bp">None</span><span class="p">,</span> <span class="o">...</span><span class="p">):</span>
<span class="o">...</span>
<span class="bp">self</span><span class="o">.</span>mode <span class="o">=</span> mode
<span class="o">...</span>
<span class="k">def</span> <span class="nf">empty_copy</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> memo<span class="o">=</span><span class="bp">None</span><span class="p">):</span>
<span class="o">...</span>
new<span class="o">.</span>mode <span class="o">=</span> deepcopy<span class="p">(</span><span class="bp">self</span><span class="o">.</span>mode<span class="p">,</span> memo<span class="p">)</span>
<span class="o">...</span>
<span class="k">def</span> <span class="nf">_latex_</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="o">...</span>
<span class="k">if</span> <span class="bp">self</span><span class="o">.</span>mode <span class="o">==</span> <span class="s">'automaton'</span><span class="p">:</span>
labels<span class="o">.</span>append<span class="p">(</span>format_transition_label<span class="p">(</span>
transition<span class="o">.</span>word_in<span class="p">))</span>
<span class="k">else</span><span class="p">:</span>
labels<span class="o">.</span>append<span class="p">(</span>format_transition_label<span class="p">(</span>
transition<span class="o">.</span>word_in<span class="p">)</span> <span class="o">+</span> <span class="s">"</span><span class="se">\\</span><span class="s">mid"</span> <span class="o">+</span> \
format_transition_label<span class="p">(</span>transition<span class="o">.</span>word_out<span class="p">))</span>
<span class="o">...</span>
<span class="k">def</span> <span class="nf">projection</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> what<span class="o">=</span><span class="s">'input'</span><span class="p">):</span>
new <span class="o">=</span> <span class="bp">self</span><span class="o">.</span>empty_copy<span class="p">()</span>
new<span class="o">.</span>mode<span class="o">=</span><span class="s">'automaton'</span>
<span class="o">...</span>
<span class="k">def</span> <span class="nf">determinisation</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="k">assert</span> <span class="bp">self</span><span class="o">.</span>mode <span class="o">==</span> <span class="s">'automaton'</span>
<span class="o">...</span>
<span class="k">def</span> <span class="nf">minimization</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> algorithm<span class="o">=</span><span class="bp">None</span><span class="p">):</span>
<span class="k">if</span> <span class="bp">self</span><span class="o">.</span>mode <span class="ow">is</span> <span class="bp">None</span><span class="p">:</span>
<span class="k">raise</span> <span class="ne">NotImplementedError</span><span class="p">,</span> <span class="s">"The mode attribute must be set."</span>
<span class="k">if</span> <span class="bp">self</span><span class="o">.</span>mode <span class="o">==</span> <span class="s">'transducer'</span><span class="p">:</span>
<span class="k">raise</span> <span class="ne">NotImplementedError</span><span class="p">,</span> <span class="s">"Minimization for Transducer is not implemented. Try the simplification method."</span>
<span class="k">if</span> <span class="ow">not</span> <span class="bp">self</span><span class="o">.</span>mode <span class="o">==</span> <span class="s">'automaton'</span><span class="p">:</span>
<span class="k">raise</span> <span class="ne">NotImplementedError</span>
<span class="o">...</span>
<span class="k">def</span> <span class="nf">simplification</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="k">if</span> <span class="bp">self</span><span class="o">.</span>mode <span class="o">!=</span> <span class="s">'transducer'</span><span class="p">:</span>
<span class="k">raise</span> <span class="ne">NotImplementedError</span><span class="p">,</span> <span class="s">"Simplification is only implemented for Transducers. For Automata, use minimization instead"</span>
<span class="o">...</span>
</pre></div></div><p>
I would leave the 70 methods not mentioned above in the class
<code>FiniteStateMachine</code>. Then, according to how each of the 7 methods are used,
I would do the following for each of them:
</p>
<ul><li><code>__init__</code>: This method can be kept as it is in the <code>FiniteStateMachine</code>
class and I believe the line <code>self.mode = mode</code> can just be deleted.
</li><li><code>empty_copy</code>: This method can be kept in the <code>FiniteStateMachine</code> and I
believe the line <code>new.mode = 'automaton'</code> can just be deleted.
</li><li><code>_latex_</code>: This method can be kept in the <code>FiniteStateMachine</code> and I
would move the code depending on the mode inside a method in the classes
<code>Automaton</code> and <code>Transducer</code>. This method could be called
<code>_transition_label</code> 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.
</li><li><code>projection</code>: This method can be kept in the <code>FiniteStateMachine</code> and
could return an instance of an Automaton.
</li><li><code>determinisation</code> and <code>minimization</code> : I would put these methods in the class <code>Automaton</code>
</li><li><code>simplification</code> : I would put this method in the class <code>Transducer</code>
</li></ul><p>
Finally, I would replace the following functions::
</p>
<div class="wiki-code"><div class="code"><pre><span class="k">def</span> <span class="nf">Transducer</span><span class="p">(</span><span class="o">*</span>args<span class="p">,</span> <span class="o">**</span>kwargs<span class="p">):</span>
<span class="o">...</span>
<span class="k">def</span> <span class="nf">Automaton</span><span class="p">(</span><span class="o">*</span>args<span class="p">,</span> <span class="o">**</span>kwargs<span class="p">):</span>
<span class="o">...</span>
</pre></div></div><p>
by classes with the same docstrings in the following way (the constructor is
stil the same actually defined for <code>FiniteStateMachine</code>)::
</p>
<div class="wiki-code"><div class="code"><pre><span class="k">class</span> <span class="nc">Transducer</span><span class="p">(</span>FiniteStateMachine<span class="p">):</span>
<span class="sd">r"""
same doctrings here as for def Transducer
"""</span>
<span class="k">def</span> <span class="nf">_transition_label</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> some_args<span class="p">):</span>
<span class="sd">r"""
Return the proper transition label.
Method used by ``_latex_`` method
"""</span>
<span class="o">...</span>
<span class="k">def</span> <span class="nf">simplification</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="o">...</span>
<span class="k">class</span> <span class="nc">Automaton</span><span class="p">(</span>FiniteStateMachine<span class="p">):</span>
<span class="sd">r"""
same doctrings here as for def Automaton
"""</span>
<span class="k">def</span> <span class="nf">_transition_label</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> some_args<span class="p">):</span>
<span class="sd">r"""
Return the proper transition label.
Method used by ``_latex_`` method
"""</span>
<span class="o">...</span>
<span class="k">def</span> <span class="nf">determinisation</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="o">...</span>
<span class="k">def</span> <span class="nf">minimization</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="o">...</span>
</pre></div></div><p>
Cheers!
</p>
<p>
Sébastien
</p>
TicketdkrennMon, 11 Nov 2013 17:47:31 GMTattachment set
https://trac.sagemath.org/ticket/15078
https://trac.sagemath.org/ticket/15078
<ul>
<li><strong>attachment</strong>
set to <em>trac_15078_fsm_automata_transducers.6.patch</em>
</li>
</ul>
TicketdkrennMon, 11 Nov 2013 17:48:54 GMT
https://trac.sagemath.org/ticket/15078#comment:21
https://trac.sagemath.org/ticket/15078#comment:21
<p>
We have worked in all the comments from above. In particular, <code>Automaton</code> and <code>Transducer</code> now inherite from <code>FiniteStateMachine</code>.
</p>
TicketdkrennThu, 14 Nov 2013 18:21:39 GMTdescription changed
https://trac.sagemath.org/ticket/15078#comment:22
https://trac.sagemath.org/ticket/15078#comment:22
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/15078?action=diff&version=22">diff</a>)
</li>
</ul>
TicketdarijSat, 16 Nov 2013 02:36:09 GMT
https://trac.sagemath.org/ticket/15078#comment:23
https://trac.sagemath.org/ticket/15078#comment:23
<p>
This needs rebasing on beta3:
</p>
<pre class="wiki">darij@travis-virtualbox:~/sage-5.13.beta3/devel/sage-main$ hg qimport ~/patches/trac_15078_fsm_automata_transducers.6.patch
adding trac_15078_fsm_automata_transducers.6.patch to series file
darij@travis-virtualbox:~/sage-5.13.beta3/devel/sage-main$ hg qpushapplying trac_15078_fsm_automata_transducers.6.patch
patching file doc/en/reference/combinat/index.rst
Hunk #1 FAILED at 78
1 out of 1 hunks FAILED -- saving rejects to file doc/en/reference/combinat/index.rst.rej
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
errors during apply, please fix and refresh trac_15078_fsm_automata_transducers.6.patch
</pre>
TicketdkrennSat, 16 Nov 2013 16:19:12 GMTattachment set
https://trac.sagemath.org/ticket/15078
https://trac.sagemath.org/ticket/15078
<ul>
<li><strong>attachment</strong>
set to <em>trac_15078_fsm_automata_transducers.7.patch</em>
</li>
</ul>
TicketdkrennSat, 16 Nov 2013 16:20:32 GMTdescription changed
https://trac.sagemath.org/ticket/15078#comment:24
https://trac.sagemath.org/ticket/15078#comment:24
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/15078?action=diff&version=24">diff</a>)
</li>
</ul>
<p>
<a class="ext-link" href="http://trac.sagemath.org/attachment/ticket/15078/trac_15078_fsm_automata_transducers.7.patch"><span class="icon"></span>http://trac.sagemath.org/attachment/ticket/15078/trac_15078_fsm_automata_transducers.7.patch</a> is rebased to 5.13.beta3.
</p>
TicketslabbeMon, 25 Nov 2013 09:36:01 GMT
https://trac.sagemath.org/ticket/15078#comment:25
https://trac.sagemath.org/ticket/15078#comment:25
<p>
Hi there, I just tested the most recent patch. All test pass. Documentation builds fine again. Correction were made after my previous comments : documentation of the input <code>FiniteStateMachine</code> is now great, new classes for <code>Automaton</code> and <code>Transducer</code> were done.
</p>
<p>
Related to the creation of the three classes, I think still another thing must be done : document the differences between them. The user of these classes will know that the three classes exist (because the documentation of one class refers to the other one). The user understand the inputs are the same, but then will ask why should he use one class instead of the other one?
</p>
<pre class="wiki"> OUTPUT:
A finite state machine.
The object creation of "Automaton" and "Transducer" is the same as
the one described here (i.e. just replace the word
"FiniteStateMachine" by "Automaton" or "Transducer").
</pre><p>
I am suggesting some fixes below that should help to answer this global question.
</p>
<ol><li>There should be a new <code>_repr_</code> method for Automaton and Transducer (I am sorry I forgot to mention this repr method in my previous comment):
</li></ol><pre class="wiki">sage: FiniteStateMachine()
Finite state machine with 0 states
sage: Automaton()
Automaton with 0 states
sage: Transducer()
Transducer with 0 states
</pre><p>
instead of
</p>
<pre class="wiki">sage: FiniteStateMachine()
finite state machine with 0 states
sage: Automaton()
finite state machine with 0 states
sage: Transducer()
finite state machine with 0 states
</pre><ol start="2"><li>The documentation of <code>FiniteStateMachine</code> should include a two line paragraph (maybe before the INPUT block) saying why the user wants to use this class and why the user should prefer to use another class like Automaton or Transducer. For instance : "For determinisation and minimisation, use Automaton class".
</li></ol><ol start="3"><li>Documentation of Automaton (and Transducer):
</li></ol><pre class="wiki">class Automaton(FiniteStateMachine):
"""
This creates an automaton, which is a special type of a finite
state machine.
See class :class:`FiniteStateMachine` for more information.
TESTS::
sage: Automaton()
finite state machine with 0 states
"""
</pre><p>
Why is it special? Mention methods that are defined for Automaton and not for <code>FiniteStateMachine</code>. Same comments for Transducer.
</p>
<p>
The first example of the documentation of <code>FiniteStateMachine</code> uses <code>word_out</code> which is not the best first example for the user using <code>Automaton</code>. So, I suggest to add an <code>EXAMPLES::</code> section in the doc of Automaton class containing the creation of at least one non empty Automaton.
</p>
<pre class="wiki">class Automaton(FiniteStateMachine):
r"""
...
The inputs are the same as for :class:`FiniteStateMachine`.
See class :class:`FiniteStateMachine` for more information.
EXAMPLES:
...
TESTS::
sage: Automaton()
finite state machine with 0 states
</pre><ol start="4"><li>A typo (finial) :
</li></ol><pre class="wiki">* "initial_states" and "final_states" -- the initial and finial
</pre>
TicketdkrennMon, 25 Nov 2013 13:31:06 GMT
https://trac.sagemath.org/ticket/15078#comment:26
https://trac.sagemath.org/ticket/15078#comment:26
<p>
Many thanks for your comments.
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15078#comment:25" title="Comment 25">slabbe</a>:
</p>
<blockquote class="citation">
<ol><li>There should be a new <code>_repr_</code> method for Automaton and Transducer (I am sorry I forgot to mention this repr method in my previous comment):
</li></ol></blockquote>
<p>
Done.
</p>
<blockquote class="citation">
<ol start="2"><li>The documentation of <code>FiniteStateMachine</code> should include a two line paragraph (maybe before the INPUT block) saying why the user wants to use this class and why the user should prefer to use another class like Automaton or Transducer. For instance : "For determinisation and minimisation, use Automaton class".
</li></ol></blockquote>
<p>
Done (Added after the output block, where Automata and Transducer are mentioned; I think this is a good place for it. Also added links to minimization, simplification,... there)
</p>
<blockquote class="citation">
<ol start="3"><li>Documentation of Automaton (and Transducer):
</li></ol><pre class="wiki">class Automaton(FiniteStateMachine):
"""
This creates an automaton, which is a special type of a finite
state machine.
</pre><p>
Why is it special? Mention methods that are defined for Automaton and not for <code>FiniteStateMachine</code>. Same comments for Transducer.
</p>
<p>
The first example of the documentation of <code>FiniteStateMachine</code> uses <code>word_out</code> which is not the best first example for the user using <code>Automaton</code>. So, I suggest to add an <code>EXAMPLES::</code> section in the doc of Automaton class containing the creation of at least one non empty Automaton.
</p>
</blockquote>
<p>
Rewritten and examples added.
</p>
<blockquote class="citation">
<ol start="4"><li>A typo (finial) :
</li></ol></blockquote>
<p>
Corrected.
</p>
<p>
These changes can be found in <a class="ext-link" href="http://trac.sagemath.org/attachment/ticket/15078/trac_15078_fsm_automata_transducers.8.patch"><span class="icon"></span>http://trac.sagemath.org/attachment/ticket/15078/trac_15078_fsm_automata_transducers.8.patch</a> (which runs in 5.13.beta3).
</p>
TicketdkrennMon, 25 Nov 2013 13:31:35 GMTattachment set
https://trac.sagemath.org/ticket/15078
https://trac.sagemath.org/ticket/15078
<ul>
<li><strong>attachment</strong>
set to <em>trac_15078_fsm_automata_transducers.8.patch</em>
</li>
</ul>
TicketdkrennMon, 25 Nov 2013 13:31:57 GMTdescription changed
https://trac.sagemath.org/ticket/15078#comment:27
https://trac.sagemath.org/ticket/15078#comment:27
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/15078?action=diff&version=27">diff</a>)
</li>
</ul>
TicketslabbeMon, 25 Nov 2013 22:39:58 GMTreviewer set
https://trac.sagemath.org/ticket/15078#comment:28
https://trac.sagemath.org/ticket/15078#comment:28
<ul>
<li><strong>reviewer</strong>
set to <em>Volker Braun, Frédéric Chapoton, Vincent Delecroix, Darij Grinberg, Sébastien Labbé</em>
</li>
</ul>
<p>
Great! Thanks for the changes and your good work answering all of the reviewers comments. I am ready to give a positive review.
</p>
<p>
Since much time passed since the start of the review, I believe everybody had a chance to give their comments. Hence, I change the status of this ticket to positive review.
</p>
<p>
Sébastien
</p>
TicketslabbeMon, 25 Nov 2013 22:48:23 GMTstatus changed
https://trac.sagemath.org/ticket/15078#comment:29
https://trac.sagemath.org/ticket/15078#comment:29
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TicketjdemeyerTue, 26 Nov 2013 10:48:08 GMTdescription changed
https://trac.sagemath.org/ticket/15078#comment:30
https://trac.sagemath.org/ticket/15078#comment:30
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/15078?action=diff&version=30">diff</a>)
</li>
</ul>
TicketjdemeyerThu, 05 Dec 2013 08:01:48 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/15078#comment:31
https://trac.sagemath.org/ticket/15078#comment:31
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.13.beta5</em>
</li>
</ul>
TicketslabbeSat, 01 Mar 2014 12:04:16 GMT
https://trac.sagemath.org/ticket/15078#comment:32
https://trac.sagemath.org/ticket/15078#comment:32
<p>
Hi,
</p>
<p>
I would like to share some comments on the code on finite state machine that was merged into Sage.
</p>
<p>
New modules sometimes takes forever (see for example <a class="closed ticket" href="https://trac.sagemath.org/ticket/10519" title="enhancement: analytic combinatorics: new code for computing asymptotics for ... (closed: fixed)">#10519</a>, <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/12996" title="enhancement: Support for one-dimensional shifts of finite type (needs_work)">#12996</a>) to go into Sage because reviewers are never happy and authors gets tired. So, for the actual ticket <a class="closed ticket" href="https://trac.sagemath.org/ticket/15078" title="enhancement: new module: finite state machines, automata, transducers (closed: fixed)">#15078</a>, I wanted things to go differently. As a reviewer, I listed a bunch of improvements. Authors made the improvements. I gave positive review. And now it is in Sage. Good!
</p>
<p>
But finally, after using the code a little bit since its inclusion into Sage, I realized that I should have asked for more improvements... Anyway, I prefer an active developpment rather than dying code on trac. So I don't regret, considering the above examples, if I gave a too quick positive review.
</p>
<p>
So, here are my comments since the inclusion into Sage:
</p>
<ul><li>The basics operations (union, concatenation, intersection, complement, Kleene star) on automaton are not implemented. This might be bad because maybe the chosen representation is not suitable to answer to those basic operations in an efficient way. Or maybe the representation is suitable... Nobody knows.
</li><li>I think for efficiency reasons there should not have a class for states and a class for transitions.
</li><li>I think the class FSMProcessIterator could be changed into a method of the class automaton or finite state machine using yield statement.
</li><li>An easy one: for now <code>__mul__</code> is chosen for intersection. It should be <code>__and__</code>. Also <code>__add__</code> is chosen for union. It should be <code>__or__</code>.
</li><li>Documentation of <a href="http://www.sagemath.org/doc/reference/combinat/sage/combinat/finite_state_machine.html">top level module</a> should not mention FSMState. Also, it should contain good examples of automaton and of transducers.
</li></ul><p>
Unfortunately, I do not have time to work on these things myself. So, I let others on the short term create ticket if they agree with one of the above.
</p>
<p>
Cheers,
</p>
<p>
Sébastien
</p>
TicketdarijSat, 01 Mar 2014 16:54:59 GMT
https://trac.sagemath.org/ticket/15078#comment:33
https://trac.sagemath.org/ticket/15078#comment:33
<p>
Please open up a new ticket -- not many people have closed tickets on their radar.
</p>
TickettmonteilSun, 02 Mar 2014 17:05:47 GMTcc changed
https://trac.sagemath.org/ticket/15078#comment:34
https://trac.sagemath.org/ticket/15078#comment:34
<ul>
<li><strong>cc</strong>
<em>tmonteil</em> added
</li>
</ul>
TicketcheubergThu, 06 Mar 2014 12:32:11 GMTcc changed
https://trac.sagemath.org/ticket/15078#comment:35
https://trac.sagemath.org/ticket/15078#comment:35
<ul>
<li><strong>cc</strong>
<em>cheuberg</em> added
</li>
</ul>
TicketskropfWed, 26 Mar 2014 16:21:01 GMT
https://trac.sagemath.org/ticket/15078#comment:36
https://trac.sagemath.org/ticket/15078#comment:36
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15078#comment:32" title="Comment 32">slabbe</a>:
</p>
<blockquote class="citation">
<ul><li>An easy one: for now <code>__mul__</code> is chosen for intersection. It should be <code>__and__</code>. Also <code>__add__</code> is chosen for union. It should be <code>__or__</code>.
</li></ul></blockquote>
<p>
In <a class="closed ticket" href="https://trac.sagemath.org/ticket/16016" title="defect: FiniteStateMachine.__and__ calls intersection and ... (closed: fixed)">#16016</a> these names are changed.
</p>
TicketcheubergSat, 12 Apr 2014 09:04:34 GMT
https://trac.sagemath.org/ticket/15078#comment:37
https://trac.sagemath.org/ticket/15078#comment:37
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15078#comment:32" title="Comment 32">slabbe</a>:
</p>
<blockquote class="citation">
<ul><li>The basics operations (union, concatenation, intersection, complement, Kleene star) on automaton are not implemented. This might be bad because maybe the chosen representation is not suitable to answer to those basic operations in an efficient way. Or maybe the representation is suitable... Nobody knows.
</li></ul></blockquote>
<p>
intersection now is in <a class="closed ticket" href="https://trac.sagemath.org/ticket/16061" title="enhancement: New method intersection (for automata and transducers) and new ... (closed: fixed)">#16061</a>
</p>
<blockquote class="citation">
<ul><li>Documentation of <a href="http://www.sagemath.org/doc/reference/combinat/sage/combinat/finite_state_machine.html">top level module</a> should not mention FSMState. Also, it should contain good examples of automaton and of transducers.
</li></ul></blockquote>
<p>
One more example has been added in <a class="closed ticket" href="https://trac.sagemath.org/ticket/16143" title="enhancement: finite_state_machine: Add an example on the Gray code into the ... (closed: fixed)">#16143</a>: Standard Binary -> Gray Code.
</p>
TicketcheubergSun, 31 May 2015 09:10:19 GMT
https://trac.sagemath.org/ticket/15078#comment:38
https://trac.sagemath.org/ticket/15078#comment:38
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15078#comment:32" title="Comment 32">slabbe</a>:
</p>
<blockquote class="citation">
<ul><li>The basics operations (union, concatenation, intersection, complement, Kleene star) on automaton are not implemented.
</li></ul></blockquote>
<p>
union is now <a class="closed ticket" href="https://trac.sagemath.org/ticket/18557" title="enhancement: Implement FiniteStateMachine.disjoint_union (and .__or__) (closed: fixed)">#18557</a>.
</p>
TicketcheubergWed, 29 Jul 2015 17:10:53 GMT
https://trac.sagemath.org/ticket/15078#comment:39
https://trac.sagemath.org/ticket/15078#comment:39
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15078#comment:32" title="Comment 32">slabbe</a>:
</p>
<blockquote class="citation">
<ul><li>The basics operations (union, concatenation, intersection, complement, Kleene star) on automaton are not implemented.
</li></ul></blockquote>
<p>
concatenation: <a class="closed ticket" href="https://trac.sagemath.org/ticket/18965" title="enhancement: New Method: FiniteStateMachine.concatenation (closed: fixed)">#18965</a>
complement: <a class="closed ticket" href="https://trac.sagemath.org/ticket/18966" title="enhancement: New Method: Automaton.complement (closed: fixed)">#18966</a>
Kleene star: <a class="closed ticket" href="https://trac.sagemath.org/ticket/18964" title="enhancement: New Method: FiniteStateMachine.kleene_star (closed: fixed)">#18964</a>
</p>
TicketjdemeyerMon, 20 Jun 2016 09:33:09 GMT
https://trac.sagemath.org/ticket/15078#comment:40
https://trac.sagemath.org/ticket/15078#comment:40
<p>
What is the rationale for this:
</p>
<pre class="wiki"> def __iadd__(self, other):
raise NotImplementedError
</pre><p>
Do you intend to implement this in the future?
</p>
TicketdkrennTue, 28 Jun 2016 15:48:44 GMT
https://trac.sagemath.org/ticket/15078#comment:41
https://trac.sagemath.org/ticket/15078#comment:41
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15078#comment:40" title="Comment 40">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
What is the rationale for this:
</p>
<pre class="wiki"> def __iadd__(self, other):
raise NotImplementedError
</pre><p>
Do you intend to implement this in the future?
</p>
</blockquote>
<p>
No, I don't think so.
</p>
Ticket