Very simple finite automaton (?)

Discussion in 'Python' started by kpp9c, Sep 23, 2009.

  1. kpp9c

    kpp9c Guest

    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
    kpp9c, Sep 23, 2009
    #1
    1. Advertising

  2. 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
    Steven D'Aprano, Sep 23, 2009
    #2
    1. Advertising

  3. 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
    Diez B. Roggisch, Sep 23, 2009
    #3
  4. kpp9c

    MCIPERF Guest

    It seems to that you have a transformational grammar.

    Gerry

    On Sep 23, 3:18 am, "Diez B. Roggisch" <> 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
    MCIPERF, Sep 23, 2009
    #4
  5. kpp9c

    akonsu Guest

    On Sep 23, 1:24 am, kpp9c <> 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
    akonsu, Sep 23, 2009
    #5
  6. kpp9c

    akonsu Guest

    On Sep 23, 11:49 am, akonsu <> wrote:
    > On Sep 23, 1:24 am, kpp9c <> 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 :)
    akonsu, Sep 23, 2009
    #6
  7. kpp9c

    duncan smith Guest

    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
    duncan smith, Sep 23, 2009
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. deejayfred
    Replies:
    0
    Views:
    526
    deejayfred
    Oct 2, 2003
  2. Roedy Green

    finite state automaton

    Roedy Green, Dec 23, 2005, in forum: Java
    Replies:
    6
    Views:
    523
    Roedy Green
    Jan 2, 2006
  3. Raymond Arthur St. Marie II of III

    very Very VERY dumb Question About The new Set( ) 's

    Raymond Arthur St. Marie II of III, Jul 23, 2003, in forum: Python
    Replies:
    4
    Views:
    449
    Raymond Hettinger
    Jul 27, 2003
  4. olivier.melcher

    Help running a very very very simple code

    olivier.melcher, May 12, 2008, in forum: Java
    Replies:
    8
    Views:
    2,244
  5. Clint Olsen
    Replies:
    2
    Views:
    145
    Clint Olsen
    Jun 29, 2004
Loading...

Share This Page