Very simple finite automaton (?)

Steven D'Aprano steven at REMOVE.THIS.cybersource.com.au
Wed Sep 23 09:13:16 CEST 2009

```On Tue, 22 Sep 2009 22:24:28 -0700, kpp9c wrote:

> I am trying to use a table (called a transition table? i dunno) to
> define a bunch of moves like so:
>
> 1 --> 2 5
> 2 --> 1 4
> 3 --> 3
> 4 --> 1
> 5 --> 4 3
>
> so that i can generate a sequence that, given an initial value, will
> continue to grow according to these rules.
...
> First, I would like to know what, precisely, this kind of process is
> called so that i can look it up. Many names are suggested but when
> googling more names and acronyms show up, maybe there are many names
> used for a variety of related things, but I could be curious to know
> exactly what this is an instance of.

No idea, sorry :)

> Second, I am not sure how to get
> started with the loop (is this an example of recursion?) and how best to
> represent the table (dictionary)? If anyone has an example of how to do
> this or a suggestion on where to start poking around, that would be
> great.

rules = {1: (2, 5), 2: (1, 4), 3: (3,), 4: (1,), 5: (4, 3)}

There are lots of ways to go from here, possibly including recursion, but
this is the way that feels most natural to me. Create a generator that
applies the rules from some input sequence:

def apply_rules(sequence):
for element in sequence:
# look it up in the global rules
values = rules[element]
# yield each of those in turn
for value in values:
yield value

And now use it to build new lists, replacing the old list each time. Here
it is in use:

>>> data = [1]
>>> for i in range(5):
...     print data
...     gen = apply_rules(data)
...     data = list(gen)
...
[1]
[2, 5]
[1, 4, 4, 3]
[2, 5, 1, 1, 3]
[1, 4, 4, 3, 2, 5, 2, 5, 3]
>>> print data  # one more to get the final result
[2, 5, 1, 1, 3, 1, 4, 4, 3, 1, 4, 4, 3, 3]

--
Steven

```