[Tutor] Automaton/transitional grammar query

[kevin parks]

I posted about this a couple weeks back, but then got horribly ill and  
dropped the ball so i was hoping to revisit.

I am not sure if this is and example of Finite Automaton or a Finite  
State Machine or perhaps it is related to a transition table or markov  
process. I think some one here told me it is called a transitional  
grammar? I am not sure. I am not a math person but i would love to  
know exactly what this is. I googled around and got lots of super  
complicated gobbledegoo all with knotty regex stuff, but what i want  
to do is much more simple. I am trying to use a table 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, that  
will continue to grow according to these rules. Starting with 1 we  
then go to 2 & 5, 2 leads us too 1 & 4, the 5 leads us to 4 & 3, then  
we iterate over 1 4 4 and 3 to get 2 5 1 1 and 3.... Like so:

1
2 5
1 4 4 3
2 5 1 1 3
1 4 4 3 2 5 2 5 3

..... etc.

Essentially, iterating over the last added items to the list, applying  
the table, appending those new items to the list, applying the table
again... etc, until the sequence reaches some predetermined number of  
iterations and quits.

[ [1], [2, 5], [1, 4] , [4, 3], [2, 5], [1], [1], [3], [1, 4], [4, 3],  
[2, 5], [2, 5], [3] ]

First, as i mentioned I would like to know what, precisely, this kind  
of process is called so that i can look it up. Second, i would l like  
to add to what i have, which seems to work. But first here is the  
code, where we left off below:

#!/usr/bin/env python

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

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

def flatten(l, ltypes=(list, tuple)):
	ltype = type(l)
	l = list(l)
	i = 0
	while i < len(l):
		while isinstance(l[i], ltypes):
			if not l[i]:
				l.pop(i)
				i -= 1
				break
			else:
				l[i:i + 1] = l[i]
		i += 1
	return ltype(l)

def test():
	data = [1]
	outlist = []
	for i in range(10):
		outlist.append(data)
		gen = apply_rules(data)
		data = list(gen)
	outlist.append(data)  # one more to get the final result
	print '\n\n', outlist, '\n\n'
	flat = flatten(outlist)
	count = 0
	for item in flat:
		print count, ',', item, ';'
		count += 1
	print '\n\n'

if __name__ == "__main__":
	test()


This all appears to work. I am not sure if this is the best way to do  
it, but for the size lists i have been generating it seems zippy.

So what? You are asking a question you already know the answer to?  
Well now I would like to have this set of rules contain some  
probabilistic branching. Instead of having my "go to" rules or grammar  
hard wired it would be good if some steps could also have weighted  
choices. So that maybe 1 --> 2 5 70% of the time but maybe it goes 1 -- 
 > 2 4  every once in a while (as in 30%). So i am not sure how to do  
that... also, it occurs to me that i could define a grammar that got  
stuck in an infinite loop if not careful. I wonder if i should add  
some mechanism to check the dictionary defined rules before  
execution.... or if that is just too hard to do and i should just be  
careful.

Meanwhile I have my trusty old weighted random func all ready to go:

import random

def windex(lst):
     '''an attempt to make a random.choose() function that makes  
weighted choices

     accepts a list of tuples with the item and probability as a pair'''

         wtotal = sum([x[1] for x in lst])
     n = random.uniform(0, wtotal)
     for item, weight in lst:
         if n &lt; weight:
             break
         n = n - weight
     return item

My question is how to apply this since i am setting up my rules in a  
dictionary, so I am confused as to how all these pieces, which work in  
isolation, would fit together. Lastly, if i add the probabilities...  
is this just a super roundabout way to make a quasi markov table? i  
dunno. But it seems like a cool way to make patterns.