[racket-users] Re: help on coding finite state automata
Chi, if you have really like finite state automata, you might be interested in a new product from Micron called the Automata Processor (AP) http://www.micronautomata.com. A single chip has (I think) 256K fsa elements operating in massive parallelism. It's particularly designed for things like "graph analysis, pattern matching, and data analytics", and can recognize large numbers of complex patterns simultaneously in streams of data at near gigabit rates. The AP is implemented as an co-processor (with up to 8 chips) for a PC, and currently has a C-based API development environment and API. It could sorely use a Racket interface and development environment. Byron On Thursday, September 3, 2015 at 7:29:33 AM UTC-7, Linh Chi Nguyen wrote: > Dear All, > I'm a complete newbie in racket and need help in coding finite state > machine/automata. Please pardon any of my ignorance. > > Thanks to this post of Tim Thornton, I see a very good way to code FSM: > http://timthornton.net/blog/id/538fa6f2f09a16ba0674813d > > I'd summarise it as following: > A finite state automaton has a number of states and each state has a name > plus many transition rules. He structures it in racket as following: > > (struct automaton (current-state states)) > (struct state (name actions)) > (struct action (event result)) > > A simple automaton can be like this: > (define simple-fsm (fsm 'A > (list (fstate 'A (list (action 0 'A) >(action 1 'B))) > (fstate 'B (list (action 0 'B) >(action 1 'A)) > > The automaton is in state A which has 2 transition rules: > - if event 1 happens, the automaton jumps to state B, > - if event 0 happens, it stays in state A. > > Then he writes some functions to update the automaton after each event (in > the post). Plus this function he omits (I guess): > (define fsm-update-state old-fsm new-state) > (struct-copy automaton old-fsm [current-state new-state])) > > HERE IS THE QUESTION: > > Using this way, after each event, there'd be a NEW automaton created. So I'm > worried about scaling. I'd like to generate 100 automata. In each cycle, I'd > pair the automata to interact for 50 times. Which means that there'd be 100 > new automata created for every single cycle. And I'd like to run at least > 1000 cycles. > > Would there be any problem with scaling? If yes, is there a way around this? > > Any kind of comments and suggestions are welcomed and appreciated, > Thank you really much, > Chi -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[racket-users] Re: help on coding finite state automata
You might want to take a look at https://github.com/mromyers/automata specifically, https://github.com/mromyers/automata/blob/master/examples.rkt and https://github.com/mromyers/automata/blob/master/machines.rkt I more or less just use the definition that was in my textbook: you provide a transition function, and the DFA or NFA just uses stream-fold to get the extended transition. I used a bunch of generics stuff to try to generalize everything past the point of practicality, but it's still reasonably fast. It's not documented, but use (in-machine? M seq) to check for acceptance, (extended-transition M start seq) for final state(s). There's also a minimization function and nfa->dfa conversion in there, but they're a bit fragile, so use at your own risk. -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[racket-users] Re: help on coding finite state automata
On Friday, September 4, 2015 at 9:31:36 AM UTC-4, Michael Myers wrote: > You might want to take a look at https://github.com/mromyers/automata > specifically, https://github.com/mromyers/automata/blob/master/examples.rkt > and https://github.com/mromyers/automata/blob/master/machines.rkt > > I more or less just use the definition that was in my textbook: you provide > a transition function, and the DFA or NFA just uses stream-fold to get the > extended transition. I used a bunch of generics stuff to try to generalize > everything past the point of practicality, but it's still reasonably > fast. > > It's not documented, but use (in-machine? M seq) to check for acceptance, > (extended-transition M start seq) for final state(s). > > There's also a minimization function and nfa->dfa conversion in there, but > they're a bit fragile, so use at your own risk. Sorry for the duplicate, this was sent yesterday, and only arived just now. -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Re: help on coding finite state automata
On Friday, September 4, 2015 at 1:34:38 AM UTC-4, Linh Chi Nguyen wrote: > Wow as much as i appreciate and try to see through all the answers, i have to > confess that i'm a first year Phd student in economics. So writing macro is > too far for me now. > > I'd just process with struct.. And see how expensive it is for my agent based > model. Hopefully i can show you the code some day, regarding all these > suggestions, if still relevant. > > Thank you, > Chi > > On 04/set/2015, at 03:25, mrmyers.random.suf...@gmail.com wrote: > > > On Thursday, September 3, 2015 at 10:29:33 AM UTC-4, Linh Chi Nguyen wrote: > >> Dear All, > >> I'm a complete newbie in racket and need help in coding finite state > >> machine/automata. Please pardon any of my ignorance. Hi Linh. One problem with doing things that way is that it creates a lot of temporary things that need to be cleaned up. The nice thing about a finite-state-machine is that you only need to keep track of one thing (current state) while it runs. In the code I linked above, a finite state machine (I use "dfa" or "deterministic finite automata") is defined as something with a 'transition function' δ(p,a) = q which, given a state p and symbol a, returns a new state q. It also has to have an initial state, and an accept? function to determine which states are to be accepted. I also wrote some helpful macros to make defining one a lot easier. You can write (define M (dfa (alphabet: '(a b)) (table: [sa : x sb] [sb : sa x] [x : x x]) (start: sa) (accept: sb))) (in-machine? M '(a b a b a b)) to accept only lists that contain alternating seqences of 'a followed by 'b. If you make your alphabet a string or list of characters, it can scan strings or lists of characters for acceptance instead. If the alphabet had been "ab", everything else could be kept the same, but you could write (in-machine? M "ababab") You can use symbols, numbers, or whatever you'd like to represent states, just list the transitions for each state in the order of the alphabet you supplied. Lastly, if you're not just interested in whether it accepts or not, and want to know the final state, use (extended-transition M s1 '(a b a b a b)) -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[racket-users] Re: help on coding finite state automata
On Thursday, September 3, 2015 at 10:29:33 AM UTC-4, Linh Chi Nguyen wrote: > Dear All, > I'm a complete newbie in racket and need help in coding finite state > machine/automata. Please pardon any of my ignorance. > > Thanks to this post of Tim Thornton, I see a very good way to code FSM: > http://timthornton.net/blog/id/538fa6f2f09a16ba0674813d > > I'd summarise it as following: > A finite state automaton has a number of states and each state has a name > plus many transition rules. He structures it in racket as following: > > (struct automaton (current-state states)) > (struct state (name actions)) > (struct action (event result)) > > A simple automaton can be like this: > (define simple-fsm (fsm 'A > (list (fstate 'A (list (action 0 'A) >(action 1 'B))) > (fstate 'B (list (action 0 'B) >(action 1 'A)) > > The automaton is in state A which has 2 transition rules: > - if event 1 happens, the automaton jumps to state B, > - if event 0 happens, it stays in state A. > > Then he writes some functions to update the automaton after each event (in > the post). Plus this function he omits (I guess): > (define fsm-update-state old-fsm new-state) > (struct-copy automaton old-fsm [current-state new-state])) > > HERE IS THE QUESTION: > > Using this way, after each event, there'd be a NEW automaton created. So I'm > worried about scaling. I'd like to generate 100 automata. In each cycle, I'd > pair the automata to interact for 50 times. Which means that there'd be 100 > new automata created for every single cycle. And I'd like to run at least > 1000 cycles. > > Would there be any problem with scaling? If yes, is there a way around this? > > Any kind of comments and suggestions are welcomed and appreciated, > Thank you really much, > Chi You might want to take a look at https://github.com/mromyers/automata specifically, https://github.com/mromyers/automata/blob/master/examples.rkt and https://github.com/mromyers/automata/blob/master/machines.rkt I more or less just use the definition that was in my textbook: you provide a transition function, and the DFA or NFA just uses stream-fold to get the extended transition. I used a bunch of generics stuff to try to generalize everything past the point of practicality, but it's still reasonably fast. It's not documented, but use (in-machine? M seq) to check for acceptance, (extended-transition M start seq) for final state(s). There's also a minimization function and nfa->dfa conversion in there, but they might have some bugs. -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Re: help on coding finite state automata
Wow as much as i appreciate and try to see through all the answers, i have to confess that i'm a first year Phd student in economics. So writing macro is too far for me now. I'd just process with struct.. And see how expensive it is for my agent based model. Hopefully i can show you the code some day, regarding all these suggestions, if still relevant. Thank you, Chi On 04/set/2015, at 03:25, mrmyers.random.suf...@gmail.com wrote: > On Thursday, September 3, 2015 at 10:29:33 AM UTC-4, Linh Chi Nguyen wrote: >> Dear All, >> I'm a complete newbie in racket and need help in coding finite state >> machine/automata. Please pardon any of my ignorance. >> >> Thanks to this post of Tim Thornton, I see a very good way to code FSM: >> http://timthornton.net/blog/id/538fa6f2f09a16ba0674813d >> >> I'd summarise it as following: >> A finite state automaton has a number of states and each state has a name >> plus many transition rules. He structures it in racket as following: >> >> (struct automaton (current-state states)) >> (struct state (name actions)) >> (struct action (event result)) >> >> A simple automaton can be like this: >> (define simple-fsm (fsm 'A >>(list (fstate 'A (list (action 0 'A) >> (action 1 'B))) >> (fstate 'B (list (action 0 'B) >> (action 1 'A)) >> >> The automaton is in state A which has 2 transition rules: >> - if event 1 happens, the automaton jumps to state B, >> - if event 0 happens, it stays in state A. >> >> Then he writes some functions to update the automaton after each event (in >> the post). Plus this function he omits (I guess): >> (define fsm-update-state old-fsm new-state) >> (struct-copy automaton old-fsm [current-state new-state])) >> >> HERE IS THE QUESTION: >> >> Using this way, after each event, there'd be a NEW automaton created. So I'm >> worried about scaling. I'd like to generate 100 automata. In each cycle, I'd >> pair the automata to interact for 50 times. Which means that there'd be 100 >> new automata created for every single cycle. And I'd like to run at least >> 1000 cycles. >> >> Would there be any problem with scaling? If yes, is there a way around this? >> >> Any kind of comments and suggestions are welcomed and appreciated, >> Thank you really much, >> Chi > > You might want to take a look at https://github.com/mromyers/automata > specifically, https://github.com/mromyers/automata/blob/master/examples.rkt > and https://github.com/mromyers/automata/blob/master/machines.rkt > I more or less just use the definition that was in my textbook: you provide a > transition function, and the DFA or NFA just uses stream-fold to get the > extended transition. I used a bunch of generics stuff to try to generalize > everything past the point of practicality, but it's still reasonably fast. > It's not documented, but use (in-machine? M seq) to check for acceptance, > (extended-transition M start seq) for final state(s). > > There's also a minimization function and nfa->dfa conversion in there, but > they might have some bugs. > > -- > You received this message because you are subscribed to a topic in the Google > Groups "Racket Users" group. > To unsubscribe from this topic, visit > https://groups.google.com/d/topic/racket-users/4o1goSwrLHA/unsubscribe. > To unsubscribe from this group and all its topics, send an email to > racket-users+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
