Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Very simple finite automaton (?)

Reply
Thread Tools

Very simple finite automaton (?)

 
 
kpp9c
Guest
Posts: n/a
 
      09-23-2009
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.


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

cheers,

kp

macosx, python2.5 & 2.6

 
Reply With Quote
 
 
 
 
Steven D'Aprano
Guest
Posts: n/a
 
      09-23-2009
On Tue, 22 Sep 2009 22:24:28 -0700, kpp9c wrote:

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

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


No idea, sorry


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


Start with a set of rules:

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

There are lots of ways to go from here, possibly including recursion, but
this is the way that feels most natural to me. Create a generator that
applies the rules from some input sequence:

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


And now use it to build new lists, replacing the old list each time. Here
it is in use:


>>> data = [1]
>>> for i in range(5):

.... print data
.... gen = apply_rules(data)
.... data = list(gen)
....
[1]
[2, 5]
[1, 4, 4, 3]
[2, 5, 1, 1, 3]
[1, 4, 4, 3, 2, 5, 2, 5, 3]
>>> print data # one more to get the final result

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



--
Steven
 
Reply With Quote
 
 
 
 
Diez B. Roggisch
Guest
Posts: n/a
 
      09-23-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
 
Reply With Quote
 
MCIPERF
Guest
Posts: n/a
 
      09-23-2009
It seems to that you have a transformational grammar.

Gerry

On Sep 23, 3:18*am, "Diez B. Roggisch" <(E-Mail Removed)> wrote:
> 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


 
Reply With Quote
 
akonsu
Guest
Posts: n/a
 
      09-23-2009
On Sep 23, 1:24*am, kpp9c <(E-Mail Removed)> wrote:
> Very simple finite automaton (?)
>
> 1 --> 2 5
> 2 --> 1 4
> 3 --> 3
> 4 --> 1
> 5 --> 4 3
>


hello,
this is a graph and you are doing depth first search.
konstantin
 
Reply With Quote
 
akonsu
Guest
Posts: n/a
 
      09-23-2009
On Sep 23, 11:49*am, akonsu <(E-Mail Removed)> wrote:
> On Sep 23, 1:24*am, kpp9c <(E-Mail Removed)> wrote:
>
> > Very simple finite automaton (?)

>
> > 1 --> 2 5
> > 2 --> 1 4
> > 3 --> 3
> > 4 --> 1
> > 5 --> 4 3

>
> hello,
> this is a graph and you are doing depth first search.
> konstantin


BREADTH first. sorry
 
Reply With Quote
 
duncan smith
Guest
Posts: n/a
 
      09-23-2009
kpp9c wrote:
> 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.
>
>
> [ [1], [2, 5], [1, 4] , [4, 3], [2, 5], [1], [1], [3], [1, 4], [4, 3],
> [2, 5], [2, 5], [3] ]
>


[snip]

I'm interested to know what you're then doing with the list. Depending
on that you might want to view it (or implement it) in terms of a
matrix, graph ...

Duncan
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Help running a very very very simple code olivier.melcher Java 8 05-12-2008 07:51 PM
finite state automaton Roedy Green Java 6 01-02-2006 04:26 PM
Does Perl combine multiple REs into a single automaton? Clint Olsen Perl Misc 2 06-29-2004 04:57 PM
Quick Book file access very very very slow Thomas Reed Computer Support 7 04-09-2004 08:09 PM
HELP PLEASE!! - Finite State Machine - Automaton - Microprogrammed System deejayfred VHDL 0 10-02-2003 01:23 AM



Advertisments