Abstract: Delayed input deterministic finite automata (D²FA) reduces the transition edges of deterministic finite automata (DFA) by introducing default edges. The relevance between DFA(^∧X)and DFA(X) is analyzed to improve the efficiency of constructing algorithm to create D2FA. A constructing algorithm is presented to create D²FA from DFA. The algorithm expresses the state of DFA(X) with the state sequence of DFA(^∧X), hence the choice of default edges is relayed on the state sequence, rather than creating actual DFA(X). Experiments show that the algorithm greatly reduces the complexity of constructing D²FA, meanwhile it ensures a lower time bounds of pattern match and capacity of reducing state transition.

Key words: deterministic finite automata, delayed input deterministic finite automata, default edge