[Tutor] Automaton/transitional grammar query

Kent Johnson kent37 at tds.net
Mon Oct 12 16:47:47 CEST 2009

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.


More information about the Tutor mailing list