Closed c50b3d32-6cb1-4b90-a060-6a332e54ef6a closed 10 years ago
Commit: c261805
Changed dependencies from #16206, #16207, #16253 to #16206, #16207, #16253, #16145
Reviewer: Clemens Heuberger
Changed author from Sara Kropf to Sara Kropf, Clemens Heuberger
I reviewed this earlier and added a few commits. Most of them minor, but I rewrote parts of Transducer.cartesian_product
and changed the default for final_function
in FiniteStateMachine.product_FiniteStateMachine
.
Minor changes in docstring
Code cleanup in prepone_output
FiniteStateMachine.projection: store doubly used list.
FiniteStateMachine.product_FiniteStateMachine: changed default for final_function
FiniteStateMachine.product_FiniteStateMachine: minor docstring edits
FiniteStateMachine.product_FiniteStateMachine: simplify code
Transducer.cartesian_product: use itertools.izip_longest
FiniteStateMachine.composition: modified docstring
FiniteStateMachine._composition_direct: states -> iter_states
FiniteStateMachine._composition_direct: provide final_function
Changed branch from u/skropf/fsm/final_output_implemented to u/dkrenn/fsm/final_output_implemented
made some minor changes; please cross-review. Apart from those, this is a positive review for me, so mark it whenever you like.
New commits:
322991f | a couple of minor changes during review |
Changed reviewer from Clemens Heuberger to Clemens Heuberger, Daniel Krenn
All changes are fine for me. Thus, I mark it as positive_review, as suggested.
Changed branch from u/dkrenn/fsm/final_output_implemented to 322991f
See also #16191.
final_word_out is used in subsequential transducers. 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.
In the following functions, final_word_out is now implemented:
FiniteStateMachine.composition
: If the output of one finite state machine is used as input of another one, then also the final output word of the first one is fed into the second one.FiniteStateMachine.output_projection
: If the automaton which recognizes the output of a transducer is constructed, then the final output word has to be the last part of a recognized input. This is implemented by constructing a new final state and adding one transition for each final output word of the original transducer. The original final states are not final anymore.FiniteStateMachine.prepone_output
: Here, final output words have to be considered like any other transition leaving a state.FiniteStateMachine.product_FiniteStateMachine
: A function which handles the combination of final output words is required if there exists non-trivial final output words.Transducer.cartesian_product
: The final output words of the new transducer consists of pairs of final output words of the original transducers.Depends on #16206 Depends on #16207 Depends on #16253 Depends on #16145
CC: @dkrenn @cheuberg
Component: combinatorics
Author: Sara Kropf, Clemens Heuberger
Branch/Commit:
322991f
Reviewer: Clemens Heuberger, Daniel Krenn
Issue created by migration from https://trac.sagemath.org/ticket/16254