non-deterministic finite automaton generation system and method, and a program that does not include the ε transition

摘要

Conversion from a normal expression via a syntax tree to an NFA not including any ϵ transition is carried out at higher speed. A system comprises initial setting means (21) and NFA converting means (22). The initial setting means (21) receives, from an input device (1), a syntax tree which is generated from a normal expression described in only two types of metacharacters ('|', '*') representing characters or matches of zero or more selections and in which a symbol ' ' representing connection and a symbol 'Φ' representing empty are used for nodes, stores the syntax tree in a syntax tree storage unit (31), carries out initial setting of an NFA to be generated, stores the NFA in an NFA storage unit (32) after the initial setting, and sends the syntax tree data read from the syntax tree storage unit (31) to the NFA converting means (22). The NFA converting means (22) reads the syntax tree data received from the initial setting means (21) and the NFA from the NFA storage unit (32), applies five conversion patterns to the respective nodes of the syntax tree to directly convert the NFA into an NFA not including ϵ transition, stores the generated NFA in the NFA storage unit (32), and outputs the NFA to the output device (4).