#15078: new module: finite state machines, automata, transducers
-------------------------------------------------+-------------------------
Reporter: dkrenn | Owner:
Type: enhancement | Status:
Priority: major | needs_review
Component: combinatorics | Milestone: sage-5.12
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 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'])]
}}}
Another example. Minimisation works fine::
{{{
sage: L = [('A', 'B', 0), ('B', 'C', 1), ('C','D',0), ('D','C', 1)]
sage: auto = Automaton(L, initial_states=['A'],
final_states=['A','C'])
sage: auto
finite state machine with 4 states
sage: auto.minimization()
finite state machine with 2 states
sage: auto.minimization().states()
[State (State 'B', State 'D'), State (State 'A', State 'C')]
}}}
Cheers!
--
Ticket URL: <http://trac.sagemath.org/ticket/15078#comment:13>
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.
