JP3827067B2 - Finite state automaton generator - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a finite state automaton creation device (Finite State Automaton, hereinafter referred to as an FSA creation device), and in particular, an FSA creation capable of reducing the amount of memory for storing FSA by reducing the number of FSA states. It relates to the device.
[0002]
[Prior art]
Conventionally, as shown in FIG. 9, one FSA (for example, FSA-A) stored in the FSA storage unit 31 is converted into one FSA in which the number of states is minimized by the state number minimizing unit 32, and output. It was stored in the FSA storage unit 33 as one FSA (FSA-A ′). The minimization method of the state number minimizing unit 32 is an algorithm for obtaining the simplest form of one FSA (eg, “Automaton / Language Theory” section 2.4 “Simple Form of Finite State Automaton”, written by Yutaka Honda, Corona Can be easily realized.
[0003]
[Problems to be solved by the invention]
However, in the past, redundant state transitions in one FSA were removed by the state number minimizing unit 32 and only one FSA was created. Therefore, by dividing one FSA into a plurality of FSAs, The total number of FSA states could not be reduced by further reducing the number of states or by combining multiple FSAs.
[0004]
The present invention has been made in view of the above-described prior art, and an object of the present invention is to reduce the total number of FSA states by dividing or / and combining FSA, and to store the FSA by reducing the number of states. An object of the present invention is to provide an FSA creation apparatus capable of reducing the amount of memory.
[0005]
[Means for Solving the Problems]
To achieve the above object, the present invention minimizes the number of states minimizing the number of states of one or more finite state automata (hereinafter referred to as FSA), and the state number minimizing unit. An equivalent partial FSA is extracted from the one or more main FSAs, and one or more main FSAs expressed using symbols of the equivalent partial FSA and an FSA dividing unit that divides into the equivalent partial FSAs The first feature is that the FSA dividing unit generates an FSA in which the sum of the number of states of the plurality of divided FSAs is smaller than the sum of the number of states of the FSA before the division. There is.
[0006]
The present invention further includes an FSA synthesis unit that extracts an equivalent partial FSA from a plurality of main FSAs minimized by the state number minimizing unit and synthesizes the equivalent FSA using the equivalent partial FSA. The second feature is that the FSA generates a FSA in which the number of states of the synthesized FSA is smaller than the sum of the number of states of the plurality of FSAs before the synthesis.
[0007]
According to the first and second features, the number of FSA states can be reduced as compared with the conventional FSA creation apparatus, and the amount of memory related to FSA storage can be reduced. .
[0008]
DETAILED DESCRIPTION OF THE INVENTION
The present invention will be described below with reference to the drawings. FIG. 1 is a block diagram showing a schematic configuration of an embodiment of the present invention.
[0009]
1 includes an FSA storage unit 1 storing a plurality of FSAs (FSA-A1 to An), a state number minimizing unit 2, an FSA dividing unit 3, and an output FSA storage unit 4. Has been.
[0010]
Next, the operation of this embodiment will be described. First, the state number minimizing unit 2 minimizes the number of states of each FSA for all the FSAs stored in the FSA storage unit 1 by the conventional method. Subsequently, the FSA dividing unit 3 performs a process of dividing one FSA into a plurality of FSAs for each FSA. For example, from one FSA (main 1) from state 1 to state 18 shown in FIG. 2, an equivalent partial FSA, that is, a partial FSA from state 2 to state 16 and a partial FSA from state 3 to state 17 Extract. Then, the partial FSA is divided from FSA (main 1), and the partial FSA is replaced with one state transition. Equivalence of FSA can be easily determined by an algorithm that calculates the equivalence of FSA (for example, “Automaton / Language Theory”, Section 2.4 “Simple Form of Finite State Automaton”, written by Tadao Honda, Corona). Can do. The same applies to the following examples.
[0011]
The equivalent part FSA is divided as (sub1), and the state 2 and the state 16 of (main1) are replaced with a symbol sub1 representing the part FSA. Similarly, the state between state 3 and state 17 of (main1) is replaced with the symbol sub1 representing the partial FSA. Then, the FSA whose symbol is replaced is newly set as (main2). By this operation, one FSA (main1) with the state number 18 is divided into an FSA (main2) with the state number 6 and a partial FSA (sub1) with the state number 8. The total number of states of the two divided FSAs is 14, which is smaller than the FSA before the division (number of states 18).
[0012]
Next, another specific example of the present embodiment will be described with reference to FIG. FIG. 3 shows an example of dividing a plurality of equivalent partial FSAs from a plurality of FSAs. In FIG. 3, the partial FSA from FSA (main1) from state 1 to state 8 is equivalent to the partial FSA from FSA (main2) from state 1 to state 8. Therefore, the partial FSA is divided as (sub1), the state 2 and the state 16 of (main1) are replaced with the symbol sub1 representing the partial FSA, and newly set as FSA (main3). Similarly, the state 1 and the state 8 of (main2) are replaced with the symbol sub1 representing the partial FSA, and newly set as FSA (main4). By this operation, the sum of the number of states of the two FSAs (main1 and main2) is 18, but the sum of the number of states of the divided FSAs (main3, main4 and sub1) is 14, which is smaller than the number of states before the division. It has become. The purpose of the FSA divider is to make the total number of FSA states after division smaller than the total number of states before division, so if the number of states is not reduced by the division operation, the division operation is not necessarily performed. There is no need to do it.
[0013]
Next, a second embodiment of the present invention will be described with reference to FIG. In this embodiment, the number of states is reduced by combining a plurality of FSAs into one FSA by the FSA combining unit 5.
[0014]
As shown in FIG. 5, the FSA synthesis unit 5 synthesizes two or more FSAs by synthesizing two or more FSA state transitions, and when the total number of states is expected to decrease. Are combined into one FSA. Whether the total number of states can be reduced by FSA synthesis can be realized by actually performing a synthesis operation in any combination of FSA and comparing the total number of states before and after synthesis.
[0015]
FIG. 5 shows an example in which two FSAs (main1 and main2) are combined to generate one FSA (main3). In FIG. 5, when two FSAs (main1 and main2) are synthesized, one FSA (main3) is obtained. By this operation, the sum of the number of states of the two FSAs (main1 and main2) is 8, but the number of states of the synthesized FSA (main3) is 5, which is smaller than the number of states before the synthesis. The purpose of the FSA synthesis unit is to make the total number of FSA states after synthesis less than the total number of states before synthesis, so if the number of states does not decrease due to the synthesis operation, the synthesis operation is not necessarily performed. There is no need to do it.
[0016]
Next, a third embodiment of the present invention will be described with reference to FIG. In this embodiment, the number of states is further reduced by putting the FSA having the number of states reduced by the FSA dividing unit 3 into the FSA combining unit 5 for synthesis.
[0017]
Next, an example of the processing flow of the FSA dividing unit 3 of FIG. 1 or 6 will be described with reference to FIG. First, a partial FSA with the largest number of states is extracted for all FSAs (step S1). It is checked whether or not the partial FSA can be extracted (step S2). If the partial FSA exists, the partial FSA division processing is temporarily performed (step S3). Next, it is checked whether or not the number of states has decreased due to partial FSA division (step S4). If the number of states decreases, partial FSA is divided from FSA (step S5). This operation is repeated until the extraction of the partial FSA fails (determination in step S2 is negative) or the number of states does not decrease due to the division of the partial FSA (determination in step S4 is negative).
[0018]
Next, an example of the processing flow of the FSA synthesis unit 5 of FIG. 4 or 6 will be described with reference to FIG. First, any two FSAs are selected for all FSAs (step S11). FSA synthesis processing is temporarily performed on the two selected FSAs (step S12). Next, it is checked whether or not the number of states has decreased due to FSA synthesis (step S13). If the number of states decreases, FSA is synthesized (step S14). This operation is repeated until all the FSA combinations are checked (step S15).
[0019]
As mentioned above, although this invention was demonstrated by suitable embodiment, this invention is not limited to this embodiment, It is clear that the various deformation | transformation which belongs to the meaning of this invention is also within the scope of this invention. .
[0020]
【The invention's effect】
As is apparent from the above description, according to the present invention, there is an effect that the total number of states of the FSA can be reduced by dividing and / or synthesizing the FSA. In addition, the reduction in the number of states has an effect of reducing the amount of memory related to FSA storage.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a schematic configuration of a first embodiment of the present invention.
FIG. 2 is an explanatory diagram of a specific example of the first embodiment of the present invention.
FIG. 3 is an explanatory diagram of another specific example of the first embodiment of the present invention.
FIG. 4 is a block diagram showing a schematic configuration of a second embodiment of the present invention.
FIG. 5 is an explanatory diagram of a specific example of the second embodiment of the present invention.
FIG. 6 is a block diagram showing a schematic configuration of a third embodiment of the present invention.
FIG. 7 is a flowchart showing the operation of the first embodiment.
FIG. 8 is a flowchart showing the operation of the second embodiment.
FIG. 9 is a block diagram showing a schematic configuration of a conventional apparatus.
[Explanation of symbols]
DESCRIPTION OF SYMBOLS 1 ... FSA storage part, 2 ... State number minimization part, 3 ... FSA division | segmentation part, 4 ... Output FSA storage part, 5 ... FSA synthetic | combination part.

Claims (4)

A state number minimizing unit for minimizing the number of states of one or more finite state automata (hereinafter referred to as FSA);
The equivalent partial FSA is extracted from one or a plurality of main FSAs minimized by the state number minimizing unit, and the one or a plurality of main FSAs represented by using symbols of the equivalent part FSA and the equivalent partial FSA And an FSA dividing unit that divides into
The FSA dividing apparatus generates an FSA in which the total number of states of a plurality of divided FSAs is smaller than the total number of states of FSAs before division. A state number minimizing unit that minimizes the number of states of a plurality of finite state automata (hereinafter referred to as FSA);
An equivalent partial FSA is extracted from a plurality of main FSAs minimized by the state number minimizing unit, and is synthesized using the equivalent partial FSA; and
The FSA synthesizing unit generates the FSA in which the number of states of the synthesized FSA is smaller than the total number of states of the plurality of FSAs before the synthesis. A state number minimizing unit for minimizing the number of states of one or more finite state automata (hereinafter referred to as FSA);
The equivalent partial FSA is extracted from one or a plurality of main FSAs minimized by the state number minimizing unit, and the one or a plurality of main FSAs represented by using symbols of the equivalent part FSA and the equivalent partial FSA An FSA splitting unit that splits into
A synthesizing unit that synthesizes the main FSA or the partial FSA divided by the FSA dividing unit,
An FSA creation apparatus characterized in that the number of synthesized FSA states is FSA which is smaller than the total number of FSA states before division. In the FSA preparation apparatus according to claim 1 or 3,
The FSA creating apparatus, wherein the FSA dividing unit further divides the partial FSA from the partial FSA.

Images