Very simple finite automaton (?)

[Steven D'Aprano]

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.

Start with a set of rules:

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