/
finite_state_machine.py
15484 lines (12377 loc) · 559 KB
/
finite_state_machine.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
# -*- coding: utf-8 -*-
r"""
Finite State Machines, Automata, Transducers
This module adds support for finite state machines, automata and
transducers.
For creating automata and transducers you can use classes
- :class:`Automaton` and :class:`Transducer`
(or the more general class :class:`FiniteStateMachine`)
or the generators
- :class:`automata <sage.combinat.finite_state_machine_generators.AutomatonGenerators>` and
:class:`transducers <sage.combinat.finite_state_machine_generators.TransducerGenerators>`
which contain :doc:`preconstructed and commonly used automata and transducers
<finite_state_machine_generators>`. See also the
:ref:`examples <finite_state_machine_examples>` below.
Contents
========
:class:`FiniteStateMachine` and derived classes :class:`Transducer` and :class:`Automaton`
------------------------------------------------------------------------------------------
Accessing parts of a finite state machine
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
.. csv-table::
:class: contentstable
:widths: 30, 70
:delim: |
:meth:`~FiniteStateMachine.state` | Get a state by its label
:meth:`~FiniteStateMachine.states` | List of states
:meth:`~FiniteStateMachine.iter_states` | Iterator over the states
:meth:`~FiniteStateMachine.initial_states` | List of initial states
:meth:`~FiniteStateMachine.iter_initial_states` | Iterator over initial states
:meth:`~FiniteStateMachine.final_states` | List of final states
:meth:`~FiniteStateMachine.iter_final_states` | Iterator over final states
:meth:`~FiniteStateMachine.transition` | Get a transition by its states and labels
:meth:`~FiniteStateMachine.transitions` | List of transitions
:meth:`~FiniteStateMachine.iter_transitions` | Iterator over the transitions
:meth:`~FiniteStateMachine.predecessors` | List of predecessors of a state
:meth:`~FiniteStateMachine.induced_sub_finite_state_machine` | Induced sub-machine
:meth:`~FiniteStateMachine.accessible_components` | Accessible components
:meth:`~FiniteStateMachine.coaccessible_components` | Coaccessible components
:meth:`~FiniteStateMachine.final_components` | Final components (connected components which cannot be left again)
(Modified) Copies
^^^^^^^^^^^^^^^^^
.. csv-table::
:class: contentstable
:widths: 30, 70
:delim: |
:meth:`~FiniteStateMachine.empty_copy` | Returns an empty deep copy
:meth:`~FiniteStateMachine.deepcopy` | Returns a deep copy
:meth:`~FiniteStateMachine.relabeled` | Returns a relabeled deep copy
:meth:`Automaton.with_output` | Extends an automaton to a transducer
Manipulation
^^^^^^^^^^^^
.. csv-table::
:class: contentstable
:widths: 30, 70
:delim: |
:meth:`~FiniteStateMachine.add_state` | Add a state
:meth:`~FiniteStateMachine.add_states` | Add states
:meth:`~FiniteStateMachine.delete_state` | Delete a state
:meth:`~FiniteStateMachine.add_transition` | Add a transition
:meth:`~FiniteStateMachine.add_transitions_from_function` | Add transitions
:attr:`~FiniteStateMachine.input_alphabet` | Input alphabet
:attr:`~FiniteStateMachine.output_alphabet` | Output alphabet
:attr:`~FiniteStateMachine.on_duplicate_transition` | Hook for handling duplicate transitions
:meth:`~FiniteStateMachine.add_from_transition_function` | Add transitions by a transition function
:meth:`~FiniteStateMachine.delete_transition` | Delete a transition
:meth:`~FiniteStateMachine.remove_epsilon_transitions` | Remove epsilon transitions (not implemented)
:meth:`~FiniteStateMachine.split_transitions` | Split transitions with input words of length ``> 1``
:meth:`~FiniteStateMachine.determine_alphabets` | Determine input and output alphabets
:meth:`~FiniteStateMachine.determine_input_alphabet` | Determine input alphabet
:meth:`~FiniteStateMachine.determine_output_alphabet` | Determine output alphabet
:meth:`~FiniteStateMachine.construct_final_word_out` | Construct final output by implicitly reading trailing letters; cf. :meth:`~FiniteStateMachine.with_final_word_out`
Properties
^^^^^^^^^^
.. csv-table::
:class: contentstable
:widths: 30, 70
:delim: |
:meth:`~FiniteStateMachine.has_state` | Checks for a state
:meth:`~FiniteStateMachine.has_initial_state` | Checks for an initial state
:meth:`~FiniteStateMachine.has_initial_states` | Checks for initial states
:meth:`~FiniteStateMachine.has_final_state` | Checks for an final state
:meth:`~FiniteStateMachine.has_final_states` | Checks for final states
:meth:`~FiniteStateMachine.has_transition` | Checks for a transition
:meth:`~FiniteStateMachine.is_deterministic` | Checks for a deterministic machine
:meth:`~FiniteStateMachine.is_complete` | Checks for a complete machine
:meth:`~FiniteStateMachine.is_connected` | Checks for a connected machine
:meth:`Automaton.is_equivalent` | Checks for equivalent automata
:meth:`~FiniteStateMachine.is_Markov_chain` | Checks for a Markov chain
:meth:`~FiniteStateMachine.is_monochromatic` | Checks whether the colors of all states are equal
:meth:`~FiniteStateMachine.number_of_words` | Determine the number of successful paths
:meth:`~FiniteStateMachine.asymptotic_moments` | Main terms of expectation and variance of sums of labels
:meth:`~FiniteStateMachine.moments_waiting_time` | Moments of the waiting time for first true output
:meth:`~FiniteStateMachine.epsilon_successors` | Epsilon successors of a state
:meth:`Automaton.shannon_parry_markov_chain` | Compute Markov chain with Parry measure
Operations
^^^^^^^^^^
.. csv-table::
:class: contentstable
:widths: 30, 70
:delim: |
:meth:`~FiniteStateMachine.disjoint_union` | Disjoint union
:meth:`~FiniteStateMachine.concatenation` | Concatenation
:meth:`~FiniteStateMachine.kleene_star` | Kleene star
:meth:`Automaton.complement` | Complement of an automaton
:meth:`Automaton.intersection` | Intersection of automata
:meth:`Transducer.intersection` | Intersection of transducers
:meth:`Transducer.cartesian_product` | Cartesian product of a transducer with another finite state machine
:meth:`~FiniteStateMachine.product_FiniteStateMachine` | Product of finite state machines
:meth:`~FiniteStateMachine.composition` | Composition (output of other is input of self)
:meth:`~FiniteStateMachine.__call__` | Composition with other finite state machine
:meth:`~FiniteStateMachine.input_projection` | Input projection (output is deleted)
:meth:`~FiniteStateMachine.output_projection` | Output projection (old output is new input)
:meth:`~FiniteStateMachine.projection` | Input or output projection
:meth:`~FiniteStateMachine.transposition` | Transposition (all transitions are reversed)
:meth:`~FiniteStateMachine.with_final_word_out` | Machine with final output constructed by implicitly reading trailing letters, cf. :meth:`~FiniteStateMachine.construct_final_word_out` for inplace version
:meth:`Automaton.determinisation` | Determinisation of an automaton
:meth:`~FiniteStateMachine.completion` | Completion of a finite state machine
:meth:`~FiniteStateMachine.process` | Process input
:meth:`~FiniteStateMachine.__call__` | Process input with shortened output
:meth:`Automaton.process` | Process input of an automaton (output differs from general case)
:meth:`Transducer.process` | Process input of a transducer (output differs from general case)
:meth:`~FiniteStateMachine.iter_process` | Return process iterator
:meth:`~FiniteStateMachine.language` | Return all possible output words
:meth:`Automaton.language` | Return all possible accepted words
Simplification
^^^^^^^^^^^^^^
.. csv-table::
:class: contentstable
:widths: 30, 70
:delim: |
:meth:`~FiniteStateMachine.prepone_output` | Prepone output where possible
:meth:`~FiniteStateMachine.equivalence_classes` | List of equivalent states
:meth:`~FiniteStateMachine.quotient` | Quotient with respect to equivalence classes
:meth:`~FiniteStateMachine.merged_transitions` | Merge transitions while adding input
:meth:`~FiniteStateMachine.markov_chain_simplification` | Simplification of a Markov chain
:meth:`Automaton.minimization` | Minimization of an automaton
:meth:`Transducer.simplification` | Simplification of a transducer
Conversion
^^^^^^^^^^
.. csv-table::
:class: contentstable
:widths: 30, 70
:delim: |
:meth:`~FiniteStateMachine.adjacency_matrix` | (Weighted) adjacency :class:`matrix <sage.matrix.constructor.MatrixFactory>`
:meth:`~FiniteStateMachine.graph` | Underlying :class:`DiGraph`
:meth:`~FiniteStateMachine.plot` | Plot
LaTeX output
++++++++++++
.. csv-table::
:class: contentstable
:widths: 30, 70
:delim: |
:meth:`~FiniteStateMachine.latex_options` | Set options
:meth:`~FiniteStateMachine.set_coordinates` | Set coordinates of the states
:meth:`~FiniteStateMachine.default_format_transition_label` | Default formatting of words in transition labels
:meth:`~FiniteStateMachine.format_letter_negative` | Format negative numbers as overlined number
:meth:`~FiniteStateMachine.format_transition_label_reversed` | Format words in transition labels in reversed order
.. SEEALSO::
:ref:`finite_state_machine_LaTeX_output`
:class:`FSMState`
-----------------
.. csv-table::
:class: contentstable
:widths: 30, 70
:delim: |
:attr:`~FSMState.final_word_out` | Final output of a state
:attr:`~FSMState.is_final` | Describes whether a state is final or not
:attr:`~FSMState.is_initial` | Describes whether a state is initial or not
:attr:`~FSMState.initial_probability` | Probability of starting in this state as part of a Markov chain
:meth:`~FSMState.label` | Label of a state
:meth:`~FSMState.relabeled` | Returns a relabeled deep copy of a state
:meth:`~FSMState.fully_equal` | Checks whether two states are fully equal (including all attributes)
:class:`FSMTransition`
----------------------
.. csv-table::
:class: contentstable
:widths: 30, 70
:delim: |
:attr:`~FSMTransition.from_state` | State in which transition starts
:attr:`~FSMTransition.to_state` | State in which transition ends
:attr:`~FSMTransition.word_in` | Input word of the transition
:attr:`~FSMTransition.word_out` | Output word of the transition
:meth:`~FSMTransition.deepcopy` | Returns a deep copy of the transition
:class:`FSMProcessIterator`
---------------------------
.. csv-table::
:class: contentstable
:widths: 30, 70
:delim: |
:meth:`~FSMProcessIterator.next` | Makes one step in processing the input tape
:meth:`~FSMProcessIterator.preview_word` | Reads a word from the input tape
:meth:`~FSMProcessIterator.result` | Returns the finished branches during process
Helper Functions
----------------
.. csv-table::
:class: contentstable
:widths: 30, 70
:delim: |
:func:`equal` | Checks whether all elements of ``iterator`` are equal
:func:`full_group_by` | Group iterable by values of some key
:func:`startswith` | Determine whether list starts with the given prefix
:func:`FSMLetterSymbol` | Returns a string associated to the input letter
:func:`FSMWordSymbol` | Returns a string associated to a word
:func:`is_FSMState` | Tests whether an object inherits from :class:`FSMState`
:func:`is_FSMTransition` | Tests whether an object inherits from :class:`FSMTransition`
:func:`is_FiniteStateMachine` | Tests whether an object inherits from :class:`FiniteStateMachine`
:func:`duplicate_transition_ignore` | Default function for handling duplicate transitions
:func:`duplicate_transition_raise_error` | Raise error when inserting a duplicate transition
:func:`duplicate_transition_add_input` | Add input when inserting a duplicate transition
.. _finite_state_machine_examples:
Examples
========
We start with a general :class:`FiniteStateMachine`. Later there will
be also an :class:`Automaton` and a :class:`Transducer`.
A simple finite state machine
-----------------------------
We can easily create a finite state machine by
::
sage: fsm = FiniteStateMachine()
sage: fsm
Empty finite state machine
By default this is the empty finite state machine, so not very
interesting. Let's create and add some states and transitions::
sage: day = fsm.add_state('day')
sage: night = fsm.add_state('night')
sage: sunrise = fsm.add_transition(night, day)
sage: sunset = fsm.add_transition(day, night)
Let us look at ``sunset`` more closely::
sage: sunset
Transition from 'day' to 'night': -|-
Note that could also have created and added the transitions directly
by::
sage: fsm.add_transition('day', 'night')
Transition from 'day' to 'night': -|-
This would have had added the states automatically, since they are
present in the transitions.
Anyhow, we got the following finite state machine::
sage: fsm
Finite state machine with 2 states
We can also obtain the underlying :class:`directed graph <DiGraph>` by
::
sage: fsm.graph()
Looped multi-digraph on 2 vertices
To visualize a finite state machine, we can use
:func:`~sage.misc.latex.latex` and run the result through LaTeX,
see the section on :ref:`finite_state_machine_LaTeX_output`
below.
Alternatively, we could have created the finite state machine above
simply by
::
sage: FiniteStateMachine([('night', 'day'), ('day', 'night')])
Finite state machine with 2 states
See :class:`FiniteStateMachine` for a lot of possibilities to create
finite state machines.
.. _finite_state_machine_recognizing_NAFs_example:
A simple Automaton (recognizing NAFs)
---------------------------------------
We want to build an automaton which recognizes non-adjacent forms
(NAFs), i.e., sequences which have no adjacent non-zeros.
We use `0`, `1`, and `-1` as digits::
sage: NAF = Automaton(
....: {'A': [('A', 0), ('B', 1), ('B', -1)], 'B': [('A', 0)]})
sage: NAF.state('A').is_initial = True
sage: NAF.state('A').is_final = True
sage: NAF.state('B').is_final = True
sage: NAF
Automaton with 2 states
Of course, we could have specified the initial and final states
directly in the definition of ``NAF`` by ``initial_states=['A']`` and
``final_states=['A', 'B']``.
So let's test the automaton with some input::
sage: NAF([0])
True
sage: NAF([0, 1])
True
sage: NAF([1, -1])
False
sage: NAF([0, -1, 0, 1])
True
sage: NAF([0, -1, -1, -1, 0])
False
sage: NAF([-1, 0, 0, 1, 1])
False
Alternatively, we could call that by
::
sage: NAF.process([0, -1, 0, 1])
(True, 'B')
which gives additionally the state in which we arrived.
We can also let an automaton act on a :doc:`word <words/words>`::
sage: W = Words([-1, 0, 1]); W
Finite and infinite words over {-1, 0, 1}
sage: w = W([1, 0, 1, 0, -1]); w
word: 1,0,1,0,-1
sage: NAF(w)
True
Recognizing NAFs via Automata Operations
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Alternatively, we can use automata operations to recognize NAFs; for
simplicity, we only use the input alphabet ``[0, 1]``. On the one
hand, we can construct such an automaton by forbidding the word
``11``::
sage: forbidden = automata.ContainsWord([1, 1], input_alphabet=[0, 1])
sage: NAF_negative = forbidden.complement()
sage: NAF_negative([1, 1, 0, 1])
False
sage: NAF_negative([1, 0, 1, 0, 1])
True
On the other hand, we can write this as a regular expression and
translate that into automata operations::
sage: zero = automata.Word([0])
sage: one = automata.Word([1])
sage: epsilon = automata.EmptyWord(input_alphabet=[0, 1])
sage: NAF_positive = (zero + one*zero).kleene_star() * (epsilon + one)
We check that the two approaches are equivalent::
sage: NAF_negative.is_equivalent(NAF_positive)
True
.. SEEALSO::
:meth:`~sage.combinat.finite_state_machine_generators.AutomatonGenerators.ContainsWord`,
:meth:`~sage.combinat.finite_state_machine_generators.AutomatonGenerators.Word`,
:meth:`~Automaton.complement`,
:meth:`~FiniteStateMachine.kleene_star`,
:meth:`~sage.combinat.finite_state_machine_generators.AutomatonGenerators.EmptyWord`,
:meth:`~Automaton.is_equivalent`.
.. _finite_state_machine_LaTeX_output:
LaTeX output
------------
We can visualize a finite state machine by converting it to LaTeX by
using the usual function :func:`~sage.misc.latex.latex`. Within LaTeX,
TikZ is used for typesetting the graphics, see the
:wikipedia:`PGF/TikZ`.
::
sage: print(latex(NAF))
\begin{tikzpicture}[auto, initial text=, >=latex]
\node[state, accepting, initial] (v0) at (3.000000, 0.000000) {$\text{\texttt{A}}$};
\node[state, accepting] (v1) at (-3.000000, 0.000000) {$\text{\texttt{B}}$};
\path[->] (v0) edge[loop above] node {$0$} ();
\path[->] (v0.185.00) edge node[rotate=360.00, anchor=north] {$1, -1$} (v1.355.00);
\path[->] (v1.5.00) edge node[rotate=0.00, anchor=south] {$0$} (v0.175.00);
\end{tikzpicture}
We can turn this into a graphical representation.
::
sage: view(NAF) # not tested
To actually see this, use the live documentation in the Sage notebook
and execute the cells in this and the previous section.
Several options can be set to customize the output, see
:meth:`~FiniteStateMachine.latex_options` for details. In particular,
we use :meth:`~FiniteStateMachine.format_letter_negative` to format
`-1` as `\overline{1}`.
::
sage: NAF.latex_options(
....: coordinates={'A': (0, 0),
....: 'B': (6, 0)},
....: initial_where={'A': 'below'},
....: format_letter=NAF.format_letter_negative,
....: format_state_label=lambda x:
....: r'\mathcal{%s}' % x.label()
....: )
sage: print(latex(NAF))
\begin{tikzpicture}[auto, initial text=, >=latex]
\node[state, accepting, initial, initial where=below] (v0) at (0.000000, 0.000000) {$\mathcal{A}$};
\node[state, accepting] (v1) at (6.000000, 0.000000) {$\mathcal{B}$};
\path[->] (v0) edge[loop above] node {$0$} ();
\path[->] (v0.5.00) edge node[rotate=0.00, anchor=south] {$1, \overline{1}$} (v1.175.00);
\path[->] (v1.185.00) edge node[rotate=360.00, anchor=north] {$0$} (v0.355.00);
\end{tikzpicture}
sage: view(NAF) # not tested
To use the output of :func:`~sage.misc.latex.latex` in your own
`\LaTeX` file, you have to include
.. code-block:: latex
\usepackage{tikz}
\usetikzlibrary{automata}
into the preamble of your file.
A simple transducer (binary inverter)
-------------------------------------
Let's build a simple transducer, which rewrites a binary word by
iverting each bit::
sage: inverter = Transducer({'A': [('A', 0, 1), ('A', 1, 0)]},
....: initial_states=['A'], final_states=['A'])
We can look at the states and transitions::
sage: inverter.states()
['A']
sage: for t in inverter.transitions():
....: print(t)
Transition from 'A' to 'A': 0|1
Transition from 'A' to 'A': 1|0
Now we apply a word to it and see what the transducer does::
sage: inverter([0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1])
[1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0]
``True`` means, that we landed in a final state, that state is labeled
``'A'``, and we also got an output.
.. _finite_state_machine_division_by_3_example:
Transducers and (in)finite Words
--------------------------------
A transducer can also act on everything iterable, in particular, on
Sage's :doc:`words <words/words>`.
::
sage: W = Words([0, 1]); W
Finite and infinite words over {0, 1}
Let us take the inverter from the previous section and feed some
finite word into it::
sage: w = W([1, 1, 0, 1]); w
word: 1101
sage: inverter(w)
word: 0010
We see that the output is again a word (this is a consequence of
calling :meth:`~Transducer.process` with ``automatic_output_type``).
We can even input something infinite like an infinite word::
sage: tm = words.ThueMorseWord(); tm
word: 0110100110010110100101100110100110010110...
sage: inverter(tm)
word: 1001011001101001011010011001011001101001...
A transducer which performs division by `3` in binary
-----------------------------------------------------
Now we build a transducer, which divides a binary number by `3`.
The labels of the states are the remainder of the division.
The transition function is
::
sage: def f(state_from, read):
....: if state_from + read <= 1:
....: state_to = 2*state_from + read
....: write = 0
....: else:
....: state_to = 2*state_from + read - 3
....: write = 1
....: return (state_to, write)
which assumes reading a binary number from left to right.
We get the transducer with
::
sage: D = Transducer(f, initial_states=[0], final_states=[0],
....: input_alphabet=[0, 1])
Let us try to divide `12` by `3`::
sage: D([1, 1, 0, 0])
[0, 1, 0, 0]
Now we want to divide `13` by `3`::
sage: D([1, 1, 0, 1])
Traceback (most recent call last):
...
ValueError: Invalid input sequence.
The raised ``ValueError``
means `13` is not divisible by `3`.
.. _finite_state_machine_gray_code_example:
Gray Code
---------
The Gray code is a binary :wikipedia:`numeral system <Numeral_system>`
where two successive values differ in only one bit, cf. the
:wikipedia:`Gray_code`. The Gray code of an integer `n` is obtained by
a bitwise xor between the binary expansion of `n` and the binary
expansion of `\lfloor n/2\rfloor`; the latter corresponds to a
shift by one position in binary.
The purpose of this example is to construct a transducer converting the
standard binary expansion to the Gray code by translating this
construction into operations with transducers.
For this construction, the least significant digit is at
the left-most position.
Note that it is easier to shift everything to
the right first, i.e., multiply by `2` instead of building
`\lfloor n/2\rfloor`. Then, we take the input xor with the right
shift of the input and forget the first letter.
We first construct a transducer shifting the binary expansion to the
right. This requires storing the previously read digit in a state.
::
sage: def shift_right_transition(state, digit):
....: if state == 'I':
....: return (digit, None)
....: else:
....: return (digit, state)
sage: shift_right_transducer = Transducer(
....: shift_right_transition,
....: initial_states=['I'],
....: input_alphabet=[0, 1],
....: final_states=[0])
sage: shift_right_transducer.transitions()
[Transition from 'I' to 0: 0|-,
Transition from 'I' to 1: 1|-,
Transition from 0 to 0: 0|0,
Transition from 0 to 1: 1|0,
Transition from 1 to 0: 0|1,
Transition from 1 to 1: 1|1]
sage: shift_right_transducer([0, 1, 1, 0])
[0, 1, 1]
sage: shift_right_transducer([1, 0, 0])
[1, 0]
The output of the shifts above look a bit weird (from a right-shift
transducer, we would expect, for example, that ``[1, 0, 0]`` was
mapped to ``[0, 1, 0]``), since we write ``None`` instead of the zero
at the left. Further, note that only `0` is listed as a final state
as we have to enforce that a most significant zero is read as the last
input letter in order to flush the last digit::
sage: shift_right_transducer([0, 1, 0, 1])
Traceback (most recent call last):
...
ValueError: Invalid input sequence.
Next, we construct the transducer performing the xor operation. We also
have to take ``None`` into account as our ``shift_right_transducer``
waits one iteration until it starts writing output. This corresponds
with our intention to forget the first letter.
::
sage: def xor_transition(state, digits):
....: if digits[0] is None or digits[1] is None:
....: return (0, None)
....: else:
....: return (0, digits[0].__xor__(digits[1]))
sage: from itertools import product
sage: xor_transducer = Transducer(
....: xor_transition,
....: initial_states=[0],
....: final_states=[0],
....: input_alphabet=list(product([None, 0, 1], [0, 1])))
sage: xor_transducer.transitions()
[Transition from 0 to 0: (None, 0)|-,
Transition from 0 to 0: (None, 1)|-,
Transition from 0 to 0: (0, 0)|0,
Transition from 0 to 0: (0, 1)|1,
Transition from 0 to 0: (1, 0)|1,
Transition from 0 to 0: (1, 1)|0]
sage: xor_transducer([(None, 0), (None, 1), (0, 0), (0, 1), (1, 0), (1, 1)])
[0, 1, 1, 0]
sage: xor_transducer([(0, None)])
Traceback (most recent call last):
...
ValueError: Invalid input sequence.
The transducer computing the Gray code is then constructed as a
:meth:`Cartesian product <Transducer.cartesian_product>` between the
shifted version and the original input (represented here by the
``shift_right_transducer`` and the :meth:`identity transducer
<sage.combinat.finite_state_machine_generators.TransducerGenerators.Identity>`,
respectively). This Cartesian product is then fed into the
``xor_transducer`` as a :meth:`composition
<FiniteStateMachine.composition>` of transducers.
::
sage: product_transducer = shift_right_transducer.cartesian_product(transducers.Identity([0, 1]))
sage: Gray_transducer = xor_transducer(product_transducer)
We use :meth:`~FiniteStateMachine.construct_final_word_out` to make sure that all output
is written; otherwise, we would have to make sure that a sufficient number of trailing
zeros is read.
::
sage: Gray_transducer.construct_final_word_out([0])
sage: Gray_transducer.transitions()
[Transition from (('I', 0), 0) to ((0, 0), 0): 0|-,
Transition from (('I', 0), 0) to ((1, 0), 0): 1|-,
Transition from ((0, 0), 0) to ((0, 0), 0): 0|0,
Transition from ((0, 0), 0) to ((1, 0), 0): 1|1,
Transition from ((1, 0), 0) to ((0, 0), 0): 0|1,
Transition from ((1, 0), 0) to ((1, 0), 0): 1|0]
There is a :meth:`prepackaged transducer
<sage.combinat.finite_state_machine_generators.TransducerGenerators.GrayCode>`
for Gray code, let's see whether they agree. We have to use
:meth:`~FiniteStateMachine.relabeled` to relabel our states with
integers.
::
sage: constructed = Gray_transducer.relabeled()
sage: packaged = transducers.GrayCode()
sage: constructed == packaged
True
Finally, we check that this indeed computes the Gray code of the first
10 non-negative integers.
::
sage: for n in srange(10):
....: Gray_transducer(n.bits())
[]
[1]
[1, 1]
[0, 1]
[0, 1, 1]
[1, 1, 1]
[1, 0, 1]
[0, 0, 1]
[0, 0, 1, 1]
[1, 0, 1, 1]
Using the hook-functions
------------------------
Let's use the :ref:`previous example "divison by
3" <finite_state_machine_division_by_3_example>` to demonstrate the optional
state and transition parameters ``hook``.
First, we define what those functions should do. In our case, this is
just saying in which state we are and which transition we take
::
sage: def state_hook(process, state, output):
....: print("We are now in State %s." % (state.label(),))
sage: from sage.combinat.finite_state_machine import FSMWordSymbol
sage: def transition_hook(transition, process):
....: print("Currently we go from %s to %s, "
....: "reading %s and writing %s." % (
....: transition.from_state, transition.to_state,
....: FSMWordSymbol(transition.word_in),
....: FSMWordSymbol(transition.word_out)))
Now, let's add these hook-functions to the existing transducer::
sage: for s in D.iter_states():
....: s.hook = state_hook
sage: for t in D.iter_transitions():
....: t.hook = transition_hook
Rerunning the process again now gives the following output::
sage: D.process([1, 1, 0, 1], check_epsilon_transitions=False)
We are now in State 0.
Currently we go from 0 to 1, reading 1 and writing 0.
We are now in State 1.
Currently we go from 1 to 0, reading 1 and writing 1.
We are now in State 0.
Currently we go from 0 to 0, reading 0 and writing 0.
We are now in State 0.
Currently we go from 0 to 1, reading 1 and writing 0.
We are now in State 1.
(False, 1, [0, 1, 0, 0])
The example above just explains the basic idea of using
hook-functions. In the following, we will use those hooks more
seriously.
.. WARNING::
The hooks of the states are also called while exploring the epsilon
successors of a state (during processing). In the example above, we
used ``check_epsilon_transitions=False`` to avoid this (and also
therefore got a cleaner output).
.. WARNING::
The arguments used when calling a hook have changed in
:trac:`16538` from ``hook(state, process)`` to
``hook(process, state, output)``. If you are using
an old-style hook, a deprecation warning is displayed.
Detecting sequences with same number of `0` and `1`
---------------------------------------------------
Suppose we have a binary input and want to accept all sequences with
the same number of `0` and `1`. This cannot be done with a finite
automaton. Anyhow, we can make usage of the hook functions to extend
our finite automaton by a counter::
sage: from sage.combinat.finite_state_machine import FSMState, FSMTransition
sage: C = FiniteStateMachine()
sage: def update_counter(process, state, output):
....: l = process.preview_word()
....: process.fsm.counter += 1 if l == 1 else -1
....: if process.fsm.counter > 0:
....: next_state = 'positive'
....: elif process.fsm.counter < 0:
....: next_state = 'negative'
....: else:
....: next_state = 'zero'
....: return FSMTransition(state, process.fsm.state(next_state),
....: l, process.fsm.counter)
sage: C.add_state(FSMState('zero', hook=update_counter,
....: is_initial=True, is_final=True))
'zero'
sage: C.add_state(FSMState('positive', hook=update_counter))
'positive'
sage: C.add_state(FSMState('negative', hook=update_counter))
'negative'
Now, let's input some sequence::
sage: C.counter = 0; C([1, 1, 1, 1, 0, 0])
(False, 'positive', [1, 2, 3, 4, 3, 2])
The result is False, since there are four `1` but only two `0`. We
land in the state ``positive`` and we can also see the values of the
counter in each step.
Let's try some other examples::
sage: C.counter = 0; C([1, 1, 0, 0])
(True, 'zero', [1, 2, 1, 0])
sage: C.counter = 0; C([0, 1, 0, 0])
(False, 'negative', [-1, 0, -1, -2])
See also methods :meth:`Automaton.process` and
:meth:`Transducer.process` (or even
:meth:`FiniteStateMachine.process`), the explanation of the parameter
``hook`` and the examples in :class:`FSMState` and
:class:`FSMTransition`, and the description and examples in
:class:`FSMProcessIterator` for more information on processing and
hooks.
REFERENCES:
.. [HKP2015] Clemens Heuberger, Sara Kropf, and Helmut Prodinger,
*Output sum of transducers: Limiting distribution and periodic
fluctuation*,
`Electron. J. Combin. 22 (2015), #P2.19 <http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p19>`_.
.. [HKW2015] Clemens Heuberger, Sara Kropf and Stephan Wagner,
*Variances and Covariances in the Central Limit Theorem for the Output
of a Transducer*, European J. Combin. 49 (2015), 167-187,
:doi:`10.1016/j.ejc.2015.03.004`.
AUTHORS:
- Daniel Krenn (2012-03-27): initial version
- Clemens Heuberger (2012-04-05): initial version
- Sara Kropf (2012-04-17): initial version
- Clemens Heuberger (2013-08-21): release candidate for Sage patch
- Daniel Krenn (2013-08-21): release candidate for Sage patch
- Sara Kropf (2013-08-21): release candidate for Sage patch
- Clemens Heuberger (2013-09-02): documentation improved
- Daniel Krenn (2013-09-13): comments from trac worked in
- Clemens Heuberger (2013-11-03): output (labels) of determinisation,
product, composition, etc. changed (for consistency),
representation of state changed, documentation improved
- Daniel Krenn (2013-11-04): whitespaces in documentation corrected
- Clemens Heuberger (2013-11-04): full_group_by added
- Daniel Krenn (2013-11-04): next release candidate for Sage patch
- Sara Kropf (2013-11-08): fix for adjacency matrix
- Clemens Heuberger (2013-11-11): fix for prepone_output
- Daniel Krenn (2013-11-11): comments from :trac:`15078` included:
docstring of FiniteStateMachine rewritten, Automaton and Transducer
inherited from FiniteStateMachine
- Daniel Krenn (2013-11-25): documentation improved according to
comments from :trac:`15078`
- Clemens Heuberger, Daniel Krenn, Sara Kropf (2014-02-21--2014-07-18):
A huge bunch of improvements. Details see
:trac:`15841`, :trac:`15847`, :trac:`15848`, :trac:`15849`, :trac:`15850`, :trac:`15922`, :trac:`15923`, :trac:`15924`,
:trac:`15925`, :trac:`15928`, :trac:`15960`, :trac:`15961`, :trac:`15962`, :trac:`15963`, :trac:`15975`, :trac:`16016`,
:trac:`16024`, :trac:`16061`, :trac:`16128`, :trac:`16132`, :trac:`16138`, :trac:`16139`, :trac:`16140`, :trac:`16143`,
:trac:`16144`, :trac:`16145`, :trac:`16146`, :trac:`16191`, :trac:`16200`, :trac:`16205`, :trac:`16206`, :trac:`16207`,
:trac:`16229`, :trac:`16253`, :trac:`16254`, :trac:`16255`, :trac:`16266`, :trac:`16355`, :trac:`16357`, :trac:`16387`,
:trac:`16425`, :trac:`16539`, :trac:`16555`, :trac:`16557`, :trac:`16588`, :trac:`16589`, :trac:`16666`, :trac:`16668`,
:trac:`16674`, :trac:`16675`, :trac:`16677`.
- Daniel Krenn (2015-09-14): cleanup :trac:`18227`
ACKNOWLEDGEMENT:
- Clemens Heuberger, Daniel Krenn and Sara Kropf are supported by the
Austrian Science Fund (FWF): P 24644-N26.
Methods
=======
"""
#*****************************************************************************
# Copyright (C) 2012--2015 Clemens Heuberger <clemens.heuberger@aau.at>
# 2012--2015 Daniel Krenn <dev@danielkrenn.at>
# 2012--2015 Sara Kropf <sara.kropf@aau.at>
#
# Distributed under the terms of the GNU General Public License (GPL)
# as published by the Free Software Foundation; either version 2 of
# the License, or (at your option) any later version.
# http://www.gnu.org/licenses/
#*****************************************************************************
from __future__ import print_function
import collections
import itertools
from six.moves import zip_longest
import sage
def full_group_by(l, key=lambda x: x):
"""
Group iterable ``l`` by values of ``key``.
INPUT:
- iterable ``l``
- key function ``key``
OUTPUT:
A list of pairs ``(k, elements)`` such that ``key(e)=k`` for all
``e`` in ``elements``.
This is similar to ``itertools.groupby`` except that lists are
returned instead of iterables and no prior sorting is required.
We do not require
- that the keys are sortable (in contrast to the
approach via ``sorted`` and ``itertools.groupby``) and
- that the keys are hashable (in contrast to the
implementation proposed in `<http://stackoverflow.com/a/15250161>`_).
However, it is required
- that distinct keys have distinct ``str``-representations.
The implementation is inspired by
`<http://stackoverflow.com/a/15250161>`_, but non-hashable keys are
allowed.
EXAMPLES::
sage: from sage.combinat.finite_state_machine import full_group_by
sage: t = [2/x, 1/x, 2/x]
sage: r = full_group_by([0, 1, 2], key=lambda i:t[i])
sage: sorted(r, key=lambda p:p[1])
[(2/x, [0, 2]), (1/x, [1])]
sage: from itertools import groupby
sage: for k, elements in groupby(sorted([0, 1, 2],
....: key=lambda i:t[i]),
....: key=lambda i:t[i]):
....: print("{} {}".format(k, list(elements)))
2/x [0]
1/x [1]
2/x [2]
Note that the behavior is different from ``itertools.groupby``
because neither `1/x<2/x` nor `2/x<1/x` does hold.
Here, the result ``r`` has been sorted in order to guarantee a
consistent order for the doctest suite.
"""
elements = collections.defaultdict(list)
original_keys = {}
for item in l:
k = key(item)
s = str(k)
if s in original_keys:
if original_keys[s]!=k:
raise ValueError("Two distinct elements with representation "