FiniteStateMachine: implement final_word_out

[cheuberg]

Implement FSMState.final_word_out in order to accomodate subsequential transducers in this package. A transducer is said to be subsequential if it is deterministic, every state is final and it has a final output word for each final state, i.e., when reading an input and reaching some final state along some path, then the final output word of this state is appended to the output labels collected along the path.

This will facilitate various transducers, e.g., when we currently have to read a sufficiently large number of zeros in order to flush some more output.

final_word_out is introduced in #16253. Now final_word_out is implemented everywhere (or there is a NotImplementedError, see #16548).

Depends on #16206 Depends on #16207 Depends on #16253

Dependencies: #16206, #16207, #16253, #16145#16254

CC: @sagetrac-skropf @dkrenn

Component: finite state machines

Author: Sara Kropf

Branch/Commit: d1f3e21

Reviewer: Clemens Heuberger, Daniel Krenn

Issue created by migration from https://trac.sagemath.org/ticket/16191

[dkrenn]

Dependencies: #16206

[cheuberg]

Changed dependencies from #16206 to #16206, #16207

[c50b3d32-6cb1-4b90-a060-6a332e54ef6a]

Changed dependencies from #16206, #16207 to #16206, #16207, #16253, #16254

[c50b3d32-6cb1-4b90-a060-6a332e54ef6a]

Description changed:

--- 
+++ 
@@ -3,8 +3,21 @@

 This will facilitate various transducers, e.g., when we currently have to read a sufficiently large number of zeros in order to flush some more output.

-Once this is implemented, `FiniteStateMachine.asymptotic_moments` (cf. #16145) should be modified: enforce that all states are final and simplify the examples by introducing final output words.
+final_word_out is introduced in #16253.
+However, final_word_out is not implemented everywhere. Currently it is implemented in 
+* `FiniteStateMachine.process` (#16206)
+* and in the LaTeX output (#16207),
+* `FiniteStateMachine.composition` (#16254),
+* `FiniteStateMachine.output_projection` (#16254),
+* `FiniteStateMachine.prepone_output` (#16254),
+* `FiniteStateMachine.product_FiniteStateMachine` (#16254),
+* `Transducer.cartesian_product` (#16254),
+but not in 
+* `FiniteStateMachine.determine_alphabets`,
+* `FiniteStateMachine.equivalence_classes`,
+* `FiniteStateMachine.transposition`,
+* `Transducer.intersection` and
+* `Transducer.simplification`.

-I do know that Sara Kropf is working on that; I currently need a ticket number in order to include a warning in `FiniteStateMachine.asymptotic_moments` (cf. #16145).
+Once final_word_out is implemented, `FiniteStateMachine.asymptotic_moments` (cf. #16145) should also be modified: enforce that all states are final and simplify the examples by introducing final output words.

-

[c50b3d32-6cb1-4b90-a060-6a332e54ef6a]

Changed dependencies from #16206, #16207, #16253, #16254 to #16206, #16207, #16253, #16145#16254

[c50b3d32-6cb1-4b90-a060-6a332e54ef6a]

Branch: u/skropf/fsm/final-word-out-problems

[c50b3d32-6cb1-4b90-a060-6a332e54ef6a]

Description changed:

--- 
+++ 
@@ -3,21 +3,5 @@

 This will facilitate various transducers, e.g., when we currently have to read a sufficiently large number of zeros in order to flush some more output.

-final_word_out is introduced in #16253.
-However, final_word_out is not implemented everywhere. Currently it is implemented in 
-* `FiniteStateMachine.process` (#16206)
-* and in the LaTeX output (#16207),
-* `FiniteStateMachine.composition` (#16254),
-* `FiniteStateMachine.output_projection` (#16254),
-* `FiniteStateMachine.prepone_output` (#16254),
-* `FiniteStateMachine.product_FiniteStateMachine` (#16254),
-* `Transducer.cartesian_product` (#16254),
-but not in 
-* `FiniteStateMachine.determine_alphabets`,
-* `FiniteStateMachine.equivalence_classes`,
-* `FiniteStateMachine.transposition`,
-* `Transducer.intersection` and
-* `Transducer.simplification`.
+final_word_out is introduced in #16253. Now final_word_out is implemented everywhere (or there is a `NotImplementedError`, see #16548).

-Once final_word_out is implemented, `FiniteStateMachine.asymptotic_moments` (cf. #16145) should also be modified: enforce that all states are final and simplify the examples by introducing final output words.
-

[c50b3d32-6cb1-4b90-a060-6a332e54ef6a]

Commit: c3f2b33

[cheuberg]

Reviewer: Clemens Heuberger

[cheuberg]

comment:8

I reviewed the patch. Builds, doctests pass. I added one commit with rather minor changes (punctuation, indentation, .. TODO:: tag) and moved the new example from the private method _composition_explorative_ to the public method composition.

Please cross-review these changes and feel free to set the status to positive_review.

---

Last 10 new commits:

13e000c	FSMState.copy also copies final_word_out
bcf3308	Transducer.asymptotic_moments only accepts transducers with all states final and transducers.GrayCode is now such a transducer.
8d29348	Correct TeX errors (raw string vs. string) in docstring (Gray Code)
ae8ec6b	Modified a few docstrings to reflect use of final output word
4927542	removed determine_alphabets=True from docstrings because it is the default anyway
ba07d56	Use iterators instead of lists
0be171e	Added examples for FiniteStateMachine.equivalence_classes
95414f5	NotImplementedError in `_composition_explorative_` if there are final word outs
c3f2b33	corrected spacing
d1f3e21	trac #16191: Reviewer Patch: Move one example; spacing; typo; punctuation

[cheuberg]

Author: Sara Kropf

[cheuberg]

Changed commit from c3f2b33 to d1f3e21

[cheuberg]

Changed branch from u/skropf/fsm/final-word-out-problems to u/cheuberg/fsm/final-word-out-problems

[dkrenn]

Changed reviewer from Clemens Heuberger to Clemens Heuberger, Daniel Krenn

[dkrenn]

comment:9

Reviewed your changes (and looked at changes of skropf as well). Fine for me.

[vbraun]

Changed branch from u/cheuberg/fsm/final-word-out-problems to d1f3e21