transducer: convenience option for process words iteratively (and showing output)

[dkrenn]

This ticket introduces a new option so that iter_processs gives the output of a transducer (when processing a word) step by step. If the transducer branches (non-deterministic transducer), an exception is raised.

This is in contrast to the existing implementation, where the full output (including information on all branches of the process) is given back in each step during iteration.

An example:

sage: inverter = Transducer({'A': [('A', 0, 1), ('A', 1, 0)]},
....:     initial_states=['A'], final_states=['A'])
sage: it = inverter.iter_process(
....:     words.FibonacciWord(), iterator_type='simple')
sage: from itertools import islice
sage: [o for o in islice(it, 0, 5)]  # only output the first 5 letters
[1, 0, 1, 1, 0]

CC: @cheuberg @sagetrac-skropf

Component: finite state machines

Keywords: sd66

Author: Daniel Krenn

Branch/Commit: 9a88fc1

Reviewer: Clemens Heuberger

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

[dkrenn]

Branch: u/dkrenn/fsm/iter_process-simple

[dkrenn]

New commits:

54c99b9	implement type-simple-iterator
9bf4d02	iter_process_simple: docstring and small renaming of parameter

[dkrenn]

Author: Daniel Krenn

[dkrenn]

Commit: 9bf4d02

[videlec]

comment:4

Even better example

sage: inverter = Transducer({'A': [('A', 0, 1), ('A', 1, 0)]},
....:                initial_states=['A'], final_states=['A'])
sage: it = inverter.iter_process(
....: words.FibonacciWord(), iterator_type='simple')
sage: u = Words([0,1])(it)
sage: u
word: 1011010110110101101011011010110110101101...

[sagetrac-git]

Changed commit from 9bf4d02 to 9376b18

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

9376b18

improved doctests (using words)

[dkrenn]

comment:6

Replying to @videlec:

Even better example

sage: inverter = Transducer({'A': [('A', 0, 1), ('A', 1, 0)]},
....:                initial_states=['A'], final_states=['A'])
sage: it = inverter.iter_process(
....: words.FibonacciWord(), iterator_type='simple')
sage: u = Words([0,1])(it)
sage: u
word: 1011010110110101101011011010110110101101...

Included. Thanks.

[videlec]

comment:7

Couldn't we do better? I tried to use inverter.process directly, but sadly it does not return only a word. My dream would be that the following just works

sage: W = Words([0,1])
sage: inverter.process(W([0,1,0])
word: 101
sage: inverter.process(words.FibonacciWord([0,1]))
word: 1011010110110101101011011010110110101101...

What do you think?

Vincent

[dkrenn]

comment:8

Replying to @videlec:

Couldn't we do better? I tried to use inverter.process directly, but sadly it does not return only a word. My dream would be that the following just works

sage: W = Words([0,1])
sage: inverter.process(W([0,1,0])
word: 101
sage: inverter.process(words.FibonacciWord([0,1]))
word: 1011010110110101101011011010110110101101...

What do you think?

Would be nice to have, but takes some effort (not sure if possible with the infinite (lazy) words). This is now #18123.

Daniel