Very simple finite automaton (?)

Diez B. Roggisch deets at nospam.web.de
Wed Sep 23 09:18:14 CEST 2009


kpp9c schrieb:
> Very simple finite automaton (?)
> 
> 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 am not a math person so i am not sure what it is called. 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 (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.
> 
> So starting with 1, we get:
> 
> 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, adding those new items to the list, applying the table
> again... etc, until the sequence reaches some predetermined number of
> iterations and quits.

What you show as example and what you describe here differ - the above 
example shows replacements, while you *talk* about adding.
> 
> 
> [ [1], [2, 5], [1, 4] , [4, 3], [2, 5], [1], [1], [3], [1, 4], [4, 3],
> [2, 5], [2, 5], [3] ]
> 
> 
> 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. 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.

It sure isn't a finite automaton. The things it reminds me of are these:

   http://en.wikipedia.org/wiki/Context-sensitive_grammar
   http://en.wikipedia.org/wiki/L-system

This is under the assumption you mean replacment, not adding.

Diez



More information about the Python-list mailing list