[Tutor] Automaton/transitional grammar query

[Kent Johnson]

On Mon, Oct 12, 2009 at 10:09 AM, kevin parks <kp8 at mac.com> wrote:
>> > 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.
>
>
> That's odd. Anyway in my program I am printing the list twice. The first
> time outlist is printed it is nested one level deep. That is just
> scaffolding. Then i pick through it one item per line having flattened it
> and print it in a format that my other program can read.

In the program you posted, outlist is a list of lists where each
sub-list is a list of integers representing one generation of the
automaton. When outlist is flattened, the result is a single list of
integers. Maybe what you posted and what you tried are different?

> I been using that flatten function since 1970. Prolly pilfered from Tim
> Peters or Effbot. Remember them guys? Awesome dudes. I wonder if they even
> use python anymore.

Yes; Tim Peters lurks on this list; Fredrik Lundh still maintains PIL, at least.

> Anyway that is from way before itertools was even a
> glimmer. Additionally, your flatten function doesn't work for me actually. I
> get:
>
> NameError: global name 'chain' is not defined

from itertools import chain


>> > 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.
>
> Yeah i don't mean an infinite loop, but more like a perpetual dance back and
> forth between to items
> that point to each other. I think I need to be careful when i define the
> rules that i don't get something like that... say if 1 goes to 4 but 4's
> rule is go to 1, for example.

That can clearly happen. There are several cases:
- every rule maps to a single symbol. In this case, each generation is
the same size as the previous generation and the pattern must repeat
at some point, as the number of patterns is limited
- all rules map to more than one symbol. In this case each generation
is longer than the previous so there can not be a repeat.
- at least one rule, but not all, maps to more than one symbol. In
this case either outcome is possible, depending on whether the
expanding rule is repeatedly hit.

Kent