The Ac algorithm The Non-deterministic Finite automaton (NFA) h e 2}-8 Is 6 3 5 (a) Goto function 123456789 f()000120303 (b) Failure function ANNaN. H
The AC Algorithm • The Non-deterministic Finite Automaton (NFA)
The AC algorithm Convert NFA to DFA (deterministic FA) 0 2 9 {h,s} input symbol next state state 0: h 6)7 0 state 1: e (a) Goto functio 23456789 f()000120303 0 (b) Failure function H
The AC Algorithm • Convert NFA to DFA (deterministic FA)
The AC algorithm The standard Ac state Node Implementation struct ac node ° int *next state256]; rule x match rule list +NEsN.4 H
The AC Algorithm • The Standard AC State Node Implementation: • struct ac_node • { • int * next_state[256]; • rule * match_rule_list; • }
The BFSM Algorithm Concentrate on DFA Mainly a novel implementation of DFA The work is based on implementation on hardware. FPGA or ASIC +NEsN.4 H
The BFSM Algorithm • Concentrate on DFA • Mainly a novel implementation of DFA • The work is based on implementation on hardware, FPGA or ASIC
The BFSM Algorithm The transition rules The description of BFSM *Rule selection Policy State Clusters for scalability purpose +NEsN.4 H
The BFSM Algorithm • The transition rules • The description of BFSM • *Rule Selection Policy • *State Clusters for scalability purpose