METHOD FOR GENERATING AUTOMATA FOR DETERMINING NESTED-DUPLICATION

摘要

Disclosed is a method for generating automata for determining nested-duplication. The method includes: a step of generating first depth automata comprising transfer conditions and states to make a transfer to the next state when sequentially reading a reference sequence comprising N characters; a step of selecting states, in which the number of early read characters is no less than a preset number, from among the states of the first depth automata, and then, generating second depth automata comprising transfer conditions and states to read characters as many as or fewer than the characters read from each of the selected states; a step of selecting states, in which the number of early read characters is no less than a preset number, from among states newly generated in the same process as the generation of the second depth automata, and then, generating N^th depth automata by repetitively generating transfer conditions and states to read characters as many as or fewer than the characters read from each of the selected states; and a step of adding a self-cycle transfer condition to repeat transfer conditions to states generated through the first to N^th depth automata. When a final state of the first depth automata is reached, nested-duplication is determined. According to the present invention, the method is capable of simply and effectively determining whether a specific sequence having a complex shape is a nested-duplication sequence of a specific reference sequence or not.;COPYRIGHT KIPO 2019