[Tutor] Automaton/transitional grammar query

[Kent Johnson]

On Mon, Oct 12, 2009 at 5:01 AM, kevin parks <kp8 at mac.com> wrote:
> First, as i mentioned I would like to know what, precisely, this kind of
> process is called so that i can look it up.

It looks like a simple cellular automaton where a cell's neighborhood
includes only the cell itself. You might be interested in
Steven Wolfram's book, "A New Kind of Science" and the many examples
on his web site:
http://www.wolframscience.com/
See Wikipedia as well. This is a very rich area.

Your set of rules is a simple context-free grammar. Generally a
context-free grammar is non-deterministic, though - there are multiple
productions from a given term - so you may not find much relevant info
by searching for this.

When you introduce the random element you are generating Markov chains.

> 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

Since you want a list at the end, rather than yielding each item you
could just build the final list using extend:
def apply_rules(sequence):
  result = []
  for element in sequence:
    result.extent(rules[element])
  return result

> 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)

I don't understand why you want to flatten outlist; when I run your
program I get one number per line, not one generation per line as you
show above.

I don't understand your flatten function, either...To flatten a single
level, which is all you need, you can use this recipe from itertools:
def flatten(listOfLists):
    return list(chain.from_iterable(listOfLists))

or use extend() again:
def flatten(sequence):
  result = []
  for element in sequence:
    result.extent(element)
  return result


>
> 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

enumerate() is simpler:
for count, item in enumerate(flat):
  print count, ',', item, ';'

>        print '\n\n'
>
> if __name__ == "__main__":
>        test()
>
>
> 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.

I don't think you will get an infinite loop. You may have a grammar
that generates a stable or repeating pattern but I don't think you
will be able to detect that without trying it.
>
> Meanwhile I have my trusty old weighted random func all ready to go:
>
> 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.

Your rules, instead of being just a list of numbers, become a list of
probability mappings. I think you want to apply the probabilities to
the whole sequence, so a single rule might be (using your example)
1: [ ((2. 5), .7), ((2. 4), .3) ]

Then change the apply_rules function to choose one of the possibilites
using your windex() function.

Kent