Constructing method of finite-state machine performing transitions according to a partial type of success function and a failure function

• US 5,495,409 A
• Filed: 10/28/1994
• Issued: 02/27/1996
• Est. Priority Date: 10/29/1993
• Status: Expired due to Fees

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Kanno, Yuji
• Primary Examiner(s): Ruggiero, Joseph
• Application Number:
  US08/331,260
• Time in Patent Office: 487 Days
• Field of Search: 364/184, 364/419.01, 364/419.11, 364/419.13, 364/419.19, 364/578, 364/DIG. 1, 364/253.1, 364/259.4, 364/225.4, 364/DIG. 2, 364/956.1 , 364/963.1, 364/963.3, 364/550, 364/551.01, 364/167.01, 364/140-147, 382/229-231, 382/305, 395/600
• US Class Current: 700/79
• CPC Class Codes: G05B 19/042 using digital processors G05B19/05 takes precedence
• CPC Class Codes: G05B 19/0426 Programming the control sequence
• CPC Class Codes: G05B 19/045 using logic state machines, consisting only of a memory or a programmable logic device containing the logic for the controlled machine and in which the state of its outputs is dependent on the state of its inputs or part of its own output states, e.g. binary decision controllers, finite state controllers
• CPC Class Codes: G05B 2219/23289 State logic control, finite state, tasks, machine, fsm
• CPC Class Codes: G05B 2219/31451 Petrinet for monitoring process
• CPC Class Codes: G05B 2219/32165 Petrinet
• CPC Class Codes: G05B 2219/32166 Convert petrinet to sequence program for cell and to control program for machine
• CPC Class Codes: G05B 2219/32353 Use elementary control task, finite state machine and loop, inhibit, synchronisation connections
• CPC Class Codes: G06F 30/3323 using formal methods, e.g. equivalence checking or property checking
• CPC Class Codes: G06F 7/00 Methods or arrangements for processing data by operating upon the order or content of the data handled logic circuits H03K19/00
• CPC Class Codes: G06V 10/75 Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g. multi-scale approaches; using context analysis; Selection of dictionaries
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A constructing method of a finite state machine with failure transitions FFM is disclosed. The machine FFM is constructed from a nondeterministic finite-state machine and a string of external inputs. States <p,q> in the machine FFM is formed of a state set q included in the nondeterministic finite-state machine and a set p defined as a subset of the state set q, and the number of states <p,q> is finite. Also, an external input c takes the machine FFM from a current state s to a next state g(s,c) and an output μ(s) is output from the next state g(s,c) in cases where a value g(s,c) of a success function g is defined, and an external input c takes the machine FFM from the current state s to a state g(f(f...f(s)...)) determined by repeatedly calculating a value f(s) of a failure function f until a value g(f(f...f(s)...)) defined is found out in cases where the value g(s,c) of the success function g is not defined. Because all of transitions from the current state s for all external inputs c are not defined by the success function g, a storage capacity for storing the machine FFM is considerably reduced.

Claims

1. A constructing method of a finite-state machine with failure transitions, comprising the steps of:

preparing a nondeterministic finite-state machine, an external input taking the nondeterministic finite-state machine from a current state to a plurality of next states;

producing a deterministic finite-state machine by utilizing the nondeterministic finite-state machine, an external input taking the deterministic finite-state machine from a current state to a next state and specifying an output at the next state, a form for specifying the next state and the output in the deterministic finite-state machine being the same as that in the nondeterministic finite-state machine or being expressed according to a pattern expression in which the form is equivalent to that in the nondeterministic finite-state machine and is convertible into that in the nondeterministic finite-state machine;

regarding a combination <

p,q>

of state sets p and q as states of the deterministic finite-state machine, the state set q being a set of states in the nondeterministic finite-state machine, and the set p being defined as a subset of the state set q;

setting an initial state s₀ of the deterministic finite-state machine to a state <

{q₀ },{q₀ }>

, q₀ denoting an initial state of the nondeterministic finite-state machine;

storing the initial state s₀ <

{q₀ },{q₀ }>

to add the initial state s₀ to a state set of the deterministic finite-state machine as an element having an unprocessed tag;

setting an output μ

(s₀) of the deterministic finite-state machine at the initial state s₀ to be a set {λ

(q₀)} having an output of the nondeterministic finite-state machine at the initial state q₀ ;

storing the output μ

(s₀);

producing a state <

φ

,φ

>

of the deterministic finite-state machine obtained in case of q=φ

;

storing the state <

φ

,φ

>

to add the state <

φ

,φ

>

to the state set of the deterministic finite-state machine as an element having a processed tag;

setting a value μ

(<

φ

,φ

>

) of an output function μ

of the deterministic finite-state machine at the state <

φ

,φ

>

to be an empty set φ

;

storing the value μ

(<

φ

,φ

>

);

setting values g(<

φ

,φ

>

,c) of a success function g for arbitrary external inputs c to be the state <

φ

,φ

>

;

storing the values g(<

φ

,φ

>

,c);

checking whether or not one or more elements respectively having an unprocessed tag exist in the state set of the deterministic finite-state machine;

selecting one of the elements <

p,q>

respectively having an unprocessed tag from the set of states of the deterministic finite-state machine as a selected element <

p,q>

in cases where one or more elements <

p,q>

respectively having an unprocessed tag exist in the set of states of the deterministic finite-state machine;

changing the selected element <

p,q>

having an unprocessed tag to a selected element <

p,q>

having a processed tag;

setting one or more values g(<

p,q>

,c) of the success function g to one or more states <

x,y>

of the deterministic finite-state machine for first external inputs c which specify a non-empty set of next states δ

(t,c) defined in the nondeterministic finite-state machine according to one of elements t of a state set p of the nondeterministic finite-state machine corresponding to a first component of the selected state <

p,q>

;

selecting a union Uδ

(t,c) of the next states δ

(t,c) of the nondeterministic finite-state machine for the first external inputs c and the elements t of the set p as values of a set y;

selecting the values of the set y or a no-empty subset of the set y as elements of a set x;

storing the values g(<

p,q>

,c)=<

x,y>

;

storing the states <

x,y>

to add the states <

x,y>

to the state set of the deterministic finite-state machine as elements respectively having an unprocessed tag in cases where the states <

x,y>

are not stored;

setting a union U{λ

(t)} of outputs λ

(t) of the nondeterministic finite-state machine for elements t of the set y as output values μ

(<

x,y>

) of the output function μ

of the deterministic finite-state machine at the states <

x,y>

in cases where the values μ

(<

x,y>

) are not defined;

storing the output values μ

(<

x,y>

)=U{λ

(t)};

setting values f(<

p,q>

) of a failure function f not depending on any of second external inputs d to states <

z,q-p>

obtained by combining a difference set q-p defined by removing elements of the subset p from elements of the set q and an arbitrary subset z of the difference set q-p in cases where each of the second external inputs d does not specify any of next states g(<

p,q>

,d) defined in the nondeterministic finite-state machine for any of elements of the state set p of the selected element <

p,q>

;

storing the values f(<

p,q>

)=<

z,q-p>

stored;

setting a union U{λ

(t)} of outputs λ

(t) of the nondeterministic finite-state machine for elements t of the difference set q-p to output values μ

(<

z,q-p>

) of the output function μ

of the deterministic finite-state machine at the states <

z,q-p>

in cases where the values μ

(<

x,y>

) of the output function μ

are not defined;

storing the output values μ

(<

z,q-p>

)=U{λ

(t)};

repeating the steps of checking whether or not one or more elements, selecting one of the elements <

p,q>

, changing the selected element <

p,q>

, setting one or more values g(<

p,q>

,c), selecting a union Uδ

(t,c), selecting the values of the set y, storing the values g(<

p,q>

,c)=<

x,y>

, storing the states <

x,y>

, setting a union U{λ

(t)}, storing the output values μ

(<

x,y>

), setting values f(<

p,q>

), storing the values f(<

p,q>

), setting a union U{λ

(t)}, and storing the output values μ

(<

z,q-p>

) until no existence of an element having an unprocessed tag is detected in the step of checking whether or not one or more elements; and

defining the deterministic finite-state machine modified in the above steps as a finite-state machine with failure transitions, wherein the number of states <

p,q>

is finite, an external input c takes the finite-state machine with failure transitions from a current state s to a next state g(s,c) and an output μ

(s) is output from the next state g(s,c) in cases where a value g(s,c) of the success function g is defined, and an external input c takes the finite-state machine with failure transitions from a current state s to a next state g(h,c) (where h=f(f(...f(s)...))) determined by repeating a process that a value f(s) of the failure function f is calculated and the value f(s) is rewritten to the symbol s until a value g(h,c) of the success function g is defined in cases where a value g(s,c) of the success function g is not defined.

2. A constructing method according to claim 1 in which the step of selecting the values of the set y comprises the steps of:

calculating a union of sets V of next states to which the first external inputs c take the nondeterministic finite-state machine from each state in the set p;

calculating a difference set V-y defined by removing elements of the set y from elements of the set V; and

setting the difference set V-y as the value of the set x.

3. A constructing method according to claim 1 in which the pattern expression in the step of preparing a deterministic finite-state machine is a regular expression or a regular transformation.

4. A transforming method of a finite-state machine with failure transitions, comprising the steps of:

preparing a finite-state machine with failure transitions in which the number of states <

p,q>

is finite, an external input c takes the finite-state machine with failure transitions from a current state s to a next state g(s,c) and an output μ

(s) is output from the next state g(s,c) in cases where a value g(s,c) of a success function g is defined, and an external input c takes the finite-state machine with failure transitions from the current state s to a next stateg g(h,c) (where h=f(f(...f(s)...))) determined by repeating a process that a value f(s) of a failure function f is calculated and the value f(s) is rewritten to the symbol s until a value g(h,c) of the success function g is defined in cases where a value g(s,c) of the success function g is not defined;

selecting an originally remarked state <

p,q>

of the finite-state machine with failure transitions and a particular external input c, a state set q being a set of states in a nondeterministic finite-state machine, and a set p being defined as a subset of the state set q;

examining whether or not a value g(<

p,q>

, c) of the success function g for the originally remarked state <

p,q> and

the particular external input c is defined;

expressing the originally remarked state <

p,q>

by a symbol P denoting a remarked state in cases where the value g(<

p,q>

,c) of the success function g is not defined;

obtaining a value h=f(f(...f(P)...)) by repeating a process that a value f(P) of the failure function f for the remarked state P is calculated and the value f(P) is rewritten to the symbol P denoting a remarked state newly defined until a value g(h,c) of the success function g is defined in the finite-state machine with failure transitions;

defining a value g(<

p,q>

,c) of the success function g as g(h,c) to determine a next state g(<

p,q>

,c)=g(h,c) for the originally remarked state <

p,q> and

the particular external input c;

storing the next state g(<

p,q>

,c);

repeating the above steps of selecting an originally remarked state, examining whether or not a value, expressing the originally remarked state, obtaining a value h=f(f(...f(P)...)), defining a value g(<

p,q>

,c) and storing the next state by changing the particular external input to one of external inputs until the next states g(<

p,q>

,c) for the originally remarked state <

p,q> and

all of the external inputs are defined and stored; and

cancelling the definition of the value f(<

p,q>

) of the failure function f for the originally remarked state <

p,q>

.

5. A transforming method according to claim 4 in which the step of selecting an originally remarked state <

p,q>

includes the steps of;

judging whether or not a storage region Sr required to store values g(<

p,q>

,c) of the success function g defined in the finite-state machine with failure transitions and values f(<

p,q>

) of the failure function f defined in the finite-state machine with failure transitions is smaller than a fixed storage region; and

preparing the originally remarked state <

p,q>

on condition that the storage region Sr is smaller than the fixed storage region, and

the step of defining a value g(<

p,q>

,c) of the success function g includes the steps of;

judging whether or not an increased storage region required to additionally store the values g(<

p,q>

,c) of the success function g for the remarked state <

p,q> and

all of the external inputs c is smaller than the fixed storage region; and

defining the values g(<

p,q>

,c) of the success function g on condition that the increased storage region is equal to or smaller than the fixed storage region.

6. A transforming method according to claim 4 in which the step of selecting an originally remarked state <

p,q>

includes the step of;

selecting the originally remarked state <

p,q>

from the states defined in the finite-state machine with failure transitions in the order placed nearer to an initial state of the finite-state machine with failure transitions.

7. A transforming method of a finite-state machine with failure transitions, comprising the steps of:

preparing a finite-state machine with failure transitions in which the number of states <

p,q>

is finite, an external input c takes the finite-state machine with failure transitions from a current state s to a next state g(s,c) and an output μ

(s) is output from the next state g(s,c) in cases where a value g(s,c) of a success function g is defined, and an external input c takes the finite-state machine with failure transitions from the current state s to a next state g(h,c) (where h=f(f(...f(s)...))) determined by repeating a process that a value f(s) of a failure function f is calculated and the value f(s) is rewritten to the symbol s until a value g(h,c) of the success function g is defined in cases where a value g(s,c) of the success function g is not defined;

counting the number of state-transitions performed by applying the failure function f for each of current states and each of external inputs while operating the finite-state machine with failure transitions, the external inputs taking the finite-state machine with failure transitions from the current states to next states;

halting the operation of the finite-state machine with failure transitions in cases where the number of state-transitions from a particular current state <

p,q>

to a particular next state f(<

p,q>

) for a particular external input c reaches a fixed number of times, a state set p being defined as a non-empty subset of a finite state set Q of a nondeterministic finite-state machine, and a set r being defined as a subset of a finite state S of the finite-state machine with failure transitions;

expressing the particular current state <

p,q>

by a symbol P denoting a remarked state;

obtaining a value h=f(f(...f(P)...)) by repeating a process that a value f(P) of the failure function f for the remarked state P is calculated and the value f(P) is rewritten to the symbol P denoting a remarked state newly defined until a value g(h,c) of the success function g is defined in the finite-state machine with failure transitions;

defining a value g(<

p,q>

,c) of the success function g as g(h,c) to determine a next state g(<

p,q>

,c)=g(h,c) for the particular current state <

p,q> and

the particular external input c;

storing the next state g(<

p,q>

,c); and

restarting the operation of the finite-state machine with failure transitions.

8. A constructing method of a pattern matching machine for collating strings of external characters written in an input document with one or more strings of referential characters and finding out one or more strings of external characters respectively agreeing with one of the strings of referential characters, comprising the steps of:

preparing a nondeterministic finite-state machine, an external input taking the nondeterministic finite-state machine from a current state to a plurality of next states;

producing a deterministic finite-state machine by utilizing the nondeterministic finite-state machine, an external character taking the deterministic finite-state machine from a current state to a next state and specifying an output at the next state, a form for specifying the next state and the output in the deterministic finite-state machine being the same as that in the nondeterministic finite-state machine or being expressed according to a pattern expression in which the form is equivalent to that in the nondeterministic finite-state machine and is convertible into that in the nondeterministic finite-state machine;

regarding a combination <

p,r>

of state sets p and r as states of the deterministic finite-state machine, the state set p being defined as a non-empty subset of a finite state set Q of the nondeterministic finite-state machine, and the state set r being defined as a subset of a finite state S of the deterministic finite-state machine;

setting an initial state s₀ of the deterministic finite-state machine to a state <

{q₀),s₀ >

, q₀ denoting an initial state of the nondeterministic finite-state machine;

storing the initial state s₀ =<

{q₀ },s₀ >

to add the initial state s₀ to a state set of the deterministic finite-state machine as an element having an unprocessed tag;

setting an output μ

(s₀) of the deterministic finite-state machine at the initial state s₀ to be a set {λ

(q₀)} having an output of the nondeterministic finite-state machine at the initial state q₀ ;

storing the output μ

(s₀);

checking whether or not one or more elements respectively having an unprocessed tag exist in the state set of the deterministic finite-state machine;

selecting an element <

p,r>

first added to the state set of the deterministic finite-state machine from the state set of the deterministic finite-state machine as a selected element in cases where one or more elements <

p,r>

respectively having an unprocessed tag exist in the state set of the deterministic finite-state machine;

changing the selected element <

p,r>

having an unprocessed tag to an selected element <

p,r>

having a processed tag;

selecting the initial state s₀ as an element of a set x in case of <

p,r>

=s₀ ;

repeating a first calculation r(<

p,r>

) for taking out a second component r of the selected state <

p,r>

one or more times until values g(.,c)=g(r(r(...r(<

p,r>

)...)),c) of a success function g are defined to obtain a state u=r(r(...r(<

p,r>

)...)) and selecting values g(u,c) of the success function g for the state u and first referential characters c as values of a set x in case of <

p,r>

≠

s₀, the first referential characters c specifying a no-empty set of next states δ

(t,c) defined in the nondeterministic finite-state machine according to one of elements t of a state set p of the nondeterministic finite-state machine which corresponds to a first component of the selected state <

p,r>

;

calculating a first union Uδ

(t,c) of next states δ

(t,c) of the nondeterministic finite-state machine for elements t of the state set p and the first referential characters c;

calculating a second union p(x)Up(r(x))Up(r(r(x)))U--Up(r(r(...r(x)...))) of a string of sets p(x),p(r(x)),p(r(r(x))), - - - ,p(r(r(...r(x)...))) obtained by applying a second calculation for taking out a first component p of the selected state <

p,r>

of the deterministic finite-state machine after the first calculation r(x) is repeated a zero time or more;

selecting difference sets Uδ

(t,c)-p(x)Up(r(x))Up(r(r(x)))U--Up(r(r(...r(x)...))) of the first and second unions for the first referential characters c as values of a set y;

setting one or more values g(<

p,r>

,c) of the success function g for the selected element <

p,r>

denoting a current state and the first referential characters c to elements of the set x in cases where the set y is the empty set;

setting the values g(<

p,r>

,c) of the success function g to the states <

y,x>

in cases where the set y is not the empty set;

storing the values g(<

p,r>

,c) of the success function g to add the values g(<

p,r>

,c) to the state set of the deterministic finite-state machine as elements respectively having an unprocessed tag in cases where the values g(<

p,r>

,c) are not stored;

calculating a third union U{δ

(z,c)} of next states δ

(z,c) in the nondeterministic finite-state machine for elements z of a state set p of the nondeterministic finite-state machine corresponding to a first component of the selected element <

p,r> and

the first referential characters c;

setting output values μ

(g(<

p,r>

,c)) of an output function of the deterministic finite-state machine at the states g(<

p,r>

,c) to a fourth union U{λ

(t)} of values λ

(t) of an output function λ

of the nondeterministic finite-state machine for elements t of the third union U{δ

(z,c)};

storing the output values μ

(g(<

p,r>

,c))=U{λ

(t)};

setting values f(g(<

p,r>

,c)) of the failure function f at the states g(<

p,r>

,c) to elements of a state set r of the nondeterministic finite-state machine corresponding to a second component of the selected element <

p,r>

in cases where one or more second referential characters c which specify next states δ

(t,c) defined in the nondeterministic finite-state machine according to one of elements t of a state set p of the nondeterministic finite-state machine corresponding to a first component of the selected element <

p,r>

exist;

storing the values f(g(<

p,r>

,c))=r;

repeating the steps of checking whether or not one or more elements, selecting an element <

p,r>

, changing the selected element, selecting the initial states, repeating a first calculation, calculating a first union, calculating a second union, selecting difference sets, setting one or more values, setting the values g(<

p,r>

,c), storing the values g(<

p,r>

,c), calculating a third union, setting output values, storing the output values, and setting values f(g(<

p,r>

,c)), storing the values f(g(<

p,r>

,c)) until no existence of an element having an unprocessed tag is detected in the step of checking whether or not one or more elements; and

defining the deterministic finite-state machine modified in the above steps as a pattern matching machine, wherein the number of states <

p,r>

is finite, a referential character c takes the pattern matching machine from a current state s to a next state g(s,c) and an output μ

(s) is output from the next state g(s,c) in cases where a value g(s,c) of the success function g is defined, and a referential character c takes the pattern matching machine from a current state s to a next state g(h,c) (where h=f(f(...f(s)...))) determined by repeating a process that a value f(s) of the failure function f is calculated and the value f(s) is rewritten to the symbol s until a value g(h,c) of the success function g is defined in cases where a value g(s,c) of the success function g is not defined.

9. A constructing method according to claim 8 in which the pattern expression in the step of preparing a deterministic finite-state machine is a regular expression or a regular transformation.

10. A transforming method of a pattern matching machine for collating strings of external characters written in an input document with one or more strings of referential characters and finding out one or more strings of external characters respectively agreeing with one of the strings of referential characters, comprising the steps of:

preparing a pattern matching machine in which the number of states <

p,r>

is finite, a referential character c takes the pattern matching machine from a current state s to a next state g(s,c) and an output μ

(s) is output from the next state g(s,c) in cases where a value g(s,c) of a success function g is defined, and a referential character c takes the pattern matching machine from the current state s to a next state h=f(f(...f(s)...)) determined by repeating a process that a value f(s) of a failure function f is calculated and the value f(s) is rewritten to the symbol s until a value g(h,c) of the success function g is defined in cases where a value g(s,c) of the success function g is not defined;

selecting an originally remarked state <

p,r>

of the pattern matching machine and a particular referential character c, a state set p being defined as a non-empty subset of a finite state set Q of a nondeterministic finite-state machine, and a set r being defined as a subset of a finite state S of the pattern matching machine;

examining whether or not a value g(<

p,r>

, c) of the success function g for the originally remarked state <

p,r> and

the particular referential character c is defined;

expressing the originally remarked state <

p,r>

by a symbol P denoting a remarked state in cases where the value g(<

p,r>

,c) of the success function g is not defined;

obtaining a value h=f(f(...f(P)...)) by repeating a process that a value f(P) of the failure function f for the remarked state P is calculated and the value f(P) is rewritten to the symbol P denoting a remarked state newly defined until a value g(h,c) of the success function g is defined in the pattern matching machine;

defining a value g(<

p,r>

,c) of the success function g as g(h,c) to determine a next state g(<

p,r>

,c)=g(h,c) for the originally remarked state <

p,r> and

the particular referential character c;

storing the next state g(<

p,r>

,c);

repeating the above steps of selecting an originally remarked state, examining whether or not a value, expressing the originally remarked state, obtaining a value h=f(f(...f(P)...)), defining a value g(<

p,r>

,c) and storing the next state by changing the particular referential character to one of referential characters until the next states g(<

p,r>

,c) for the originally remarked state <

p,r> and

all of the referential characters are defined and stored; and

cancelling the definition of the value f(<

p,r>

) of the failure function f for the originally remarked state <

p,r>

.

11. A transforming method according to claim 10 in which the step of selecting an originally remarked state <

p,r>

includes the steps of;

judging whether or not a storage region Sr required to store values g(<

p,r>

,c) of the success function g defined in the pattern matching machine and values f(<

p,r>

) of the failure function f defined in the pattern matching machine is smaller than a fixed storage region; and

preparing the originally remarked state <

p,r>

on condition that the storage region Sr is smaller than the fixed storage region, and

the step of defining a value g(<

p,r>

,c) of the success function g includes the steps of;

judging whether or not an increased storage region required to additionally store the values g(<

p,r>

,c) of the success function g for the remarked state <

p,r> and

all of the referential characters c is smaller than the fixed storage region; and

defining the values g(<

p,r>

,c) of the success function g on condition that the increased storage region is equal to or smaller than the fixed storage region.

12. A transforming method according to claim 10 in which the step of selecting an originally remarked state <

p,r>

includes the step of;

selecting the originally remarked state <

p,r>

from the states defined in the pattern matching machine in the order placed nearer to an initial state of the pattern matching machine.

13. A transforming method of a pattern matching machine for collating strings of external characters written in an input document with one or more strings of referential characters and finding out one or more strings of external characters respectively agreeing with one of the strings of referential characters, comprising the steps of:

preparing a pattern matching machine in which the number of states <

p,r>

is finite, a referential characters c takes the pattern matching machine from a current state s to a next state g(s,c) and an output μ

(s) is output from the next state g(s,c) in cases where a value g(s,c) of a success function g is defined, and a referential characters c takes the pattern matching machine from the current state s to a next state g(h,c) (where h=f(f(...f(s)...))) determined by repeating a process that a value f(s) of a failure function f is calculated and the value f(s) is rewritten to the symbol s until a value g(h,c) of the success function g is defined in cases where a value g(s,c) of the success function g is not defined;

counting the number of state-transitions performed by applying the failure function f for each of current states and each of referential characters while operating the pattern matching machine, the referential characters taking the pattern matching machine from the current states to next states;

halting the operation of the pattern matching machine in cases where the number of state-transitions from a particular current state <

p,r>

to a particular next state f(<

p,r>

) for a particular referential characters c reaches a fixed number of times, a state set p being defined as a non-empty subset of a finite state set Q of a nondeterministic finite-state machine, and a set r being defined as a subset of a finite state S of the pattern matching machine;

expressing the particular current state <

p,r>

by a symbol P denoting a remarked state;

obtaining a value h=f(f(...f(P)...)) by repeating a process that a value f(P) of the failure function f for the remarked state P is calculated and the value f(P) is rewritten to the symbol P denoting a remarked state newly defined until a value g(h,c) of the success function g is defined in the pattern matching machine;

defining a value g(<

p,r>

,c) of the success function g as g(h,c) to determine a next state g(<

p,r>

,c)=g(h,c) for the particular current state <

p,r> and

the particular referential characters c;

storing the next state g(<

p,r>

,c); and

restarting the operation of the pattern matching machine.

14. An automatic product inspection system, comprising:

finite-state machine with failure transitions constructing means for constructing a finite-state machine with failure transitions from a nondeterministic finite-state machine according to a constructing method, the constructing method comprising the steps of

preparing the nondeterministic finite-state machine, an external input taking the nondeterministic finite-state machine from a current state to a plurality of next states,

producing a deterministic finite-state machine by utilizing the nondeterministic finite-state machine, an external input taking the deterministic finite-state machine from a current state to a next state and specifying an output at the next state, a form for specifying the next state and the output in the deterministic finite-state machine being the same as that in the nondeterministic finite-state machine or being expressed according to a pattern expression in which the form is equivalent to that in the nondeterministic finite-state machine and is convertible into that in the nondeterministic finite-state machine,

regarding a combination <

p,q>

of state sets p and q as states of the deterministic finite-state machine, the state set q being a set of states in the nondeterministic finite-state machine, and the set p being defined as a subset of the state set q,

setting an initial state s₀ of the deterministic finite-state machine to a state <

{q₀ },{q₀ }>

, q₀ denoting an initial state of the nondeterministic finite-state machine,

storing the initial state s₀ =<

{q₀),{q₀)>

to add the initial state s₀ to a state set of the deterministic finite-state machine as an element having an unprocessed tag,

setting an output μ

(s₀) of the deterministic finite-state machine at the initial state s₀ to be a set {λ

(q₀)) having an output of the nondeterministic finite-state machine at the initial state q₀,

storing the output μ

(s₀),

producing a state <

φ

,φ

>

of the deterministic finite-state machine obtained in case of q=φ

,

storing the state <

φ

,φ

>

to add the state <

φ

,φ

>

to the state set of the deterministic finite-state machine as an element having a processed tag,

setting a value μ

(<

φ

,φ

>

) of an output function μ

of the deterministic finite-state machine at the state <

φ

,φ

>

to be an empty set φ

,

storing the value μ

(<

φ

,φ

>

),

setting values g(<

φ

,φ

>

,c) of a success function g for arbitrary external inputs c to be the state <

φ

,φ

>

,

storing the values g(<

φ

,φ

>

,c),

checking whether or not one or more elements respectively having an unprocessed tag exist in the state set of the deterministic finite-state machine,

selecting one of the elements <

p,q>

respectively having an unprocessed tag from the set of states of the deterministic finite-state machine as a selected element <

p,q>

in cases where one or more elements <

p,q>

respectively having an unprocessed tag exist in the set of states of the deterministic finite-state machine,

changing the selected element <

p,q>

having an unprocessed tag to a selected element <

p,q>

having a processed tag,

setting one or more values g(<

p,q>

,c) of the success function g to one or more states <

x,y>

of the deterministic finite-state machine for first external inputs c which specify a non-empty set of next states δ

(t,c) defined in the nondeterministic finite-state machine according to one of elements t of a state set p of the nondeterministic finite-state machine corresponding to a first component of the selected state <

p,q>

,

selecting a union Uδ

(t,c) of the next states δ

(t,c) of the nondeterministic finite-state machine for the first external inputs c and the elements t of the set p as values of a set y,

selecting the values of the set y or a no-empty subset of the set y as elements of a set x,

storing the values g(<

p,q>

,c)=<

x,y>

,

storing the states <

x,y>

to add the states <

x,y>

to the state set of the deterministic finite-state machine as elements respectively having an unprocessed tag in cases where the states <

x,y>

are not stored,

setting a union U{λ

(t)} of outputs λ

(t) of the nondeterministic finite-state machine for elements t of the set y as output values μ

(<

x,y>

) of the output function μ

of the deterministic finite-state machine at the states <

x,y>

in cases where the values μ

(<

x,y>

) are not defined,

storing the output values μ

(<

x,y>

)=U{λ

(t)},

setting values f(<

p,q>

) of a failure function f not depending on any of second external inputs d to states <

z,q-p>

obtained by combining a difference set q-p defined by removing elements of the subset p from elements of the set q and an arbitrary subset z of the difference set q-p in cases where each of the second external inputs d does not specify any of next states g(<

p,q>

,d) defined in the nondeterministic finite-state machine for any of elements of the state set p of the selected element <

p,q>

,

storing the values f(<

p,q>

)=<

z,q-p>

stored,

setting a union U{λ

(t)} of outputs λ

(t) of the nondeterministic finite-state machine for elements t of the difference set q-p to output values μ

(<

z,q-p>

) of the output function μ

of the deterministic finite-state machine at the states <

z,q-p>

in cases where the values μ

(<

x,y>

) of the output function μ

are not defined,

storing the output values μ

(<

z,q-p>

)=U{λ

(t)},

repeating the steps of checking whether or not one or more elements, selecting one of the elements <

p,q>

, changing the selected element <

p,q>

, setting one or more values g(<

p,q>

,c), selecting a union Uδ

(t,c), selecting the values of the set y, storing the values g(<

p,q>

,c)=<

x,y>

, storing the states <

x,y>

, setting a union U{λ

(t)}, storing the output values μ

(<

x,y>

), setting values f(<

p,q>

), storing the values f(<

p,q>

), setting a union U{λ

(t)}, and storing the output values μ

(<

z,q-p>

) until no existence of an element having an unprocessed tag is detected in the step of checking whether or not one or more elements, and

defining the deterministic finite-state machine modified in the above steps as a finite-state machine with failure transitions, wherein the number of states <

p,q>

is finite, an external input c takes the finite-state machine with failure transitions from a current state s to a next state g(s,c) and an output μ

(s) is output from the next state g(s,c) in cases where a value g(s,c) of the success function g is defined, and an external input c takes the finite-state machine with failure transitions from a current state s to a next state g(h,c) (where h=f(f(...f(s)...))) determined by repeating a process that a value f(s) of the failure function f is calculated and the value f(s) is rewritten to the symbol s until a value g(h,c) of the success function g is defined in cases where a value g(s,c) of the success function g is not defined;

detecting means for detecting a plurality of types of features of a product at one time every prescribed time and outputting time-sequentially a string of inspecting values Iv, each of the inspecting values Iv indicating particular types of features of the product detected at one time;

control means for performing state-transitions of the finite-state machine with failure transitions constructed in the finite-state machine with failure transitions constructing means by utilizing the string of inspecting values Iv produced in the detecting means, each of the inspecting values Iv taking the finite-state machine with failure transitions from a current state s to a next state g(s,Iv) and an output μ

(s) being output from the next state g(s,Iv) in cases where a value g(s,Iv) of the success function g is defined, and each of the inspecting values Iv taking the finite-state machine with failure transitions from the current state s to a next state f(s) determined by a value f(s) of the failure function f in cases where the value g(s,Iv) of the success function g is not defined; and

action means for processing the product according to the outputs μ

(s) produced in the control means.

15. An automatic product inspection system, comprising:

finite-state machine with failure transitions transforming means for transforming, according to a transforming method, a finite-state machine with failure transitions in which the number of states <

p,q>

is finite, an external input c takes the finite-state machine with failure transitions from a current state s to a next state g(s,c) and an output μ

(s) is output from the next state g(s,c) in cases where a value g(s,c) of a success function g is defined, and an external input c takes the finite-state machine with failure transitions from the current state s to a next state g(h,c) (where h=f(f(...f(s)...))) determined by repeating a process that a value f(s) of the failure function f is calculated and the value f(s) is rewritten to the symbol s until a value g(h,c) of the success function g is defined in cases where a value g(s,c) of the success function g is not defined, the transforming method comprising the steps of

selecting an originally remarked state <

p,q>

of the finite-state machine with failure transitions and a particular external input c, a state set q being a set of states in a nondeterministic finite-state machine, and a set p being defined as a subset of the state set q,

examining whether or not a value g(<

p,q>

, c) of the success function g for the originally remarked state <

p,q> and

the particular external input c is defined,

expressing the originally remarked state <

p,q>

by a symbol P denoting a remarked state in cases where the value g(<

p,q>

,c) of the success function g is not defined,

obtaining a value h=f(f(...f(P)...)) by repeating a process that a value f(P) of the failure function f for the remarked state P is calculated and the value f(P) is rewritten to the symbol P denoting a remarked state newly defined until a value g(h,c) of the success function g is defined in the finite-state machine with failure transitions,

defining a value g(<

p,q>

,c) of the success function g as g(h,c) to determine a next state g(<

p,q>

,c)=g(h,c) for the originally remarked state <

p,q> and

the particular external input c,

storing the next state g(<

p,q>

,c),

repeating the above steps of selecting an originally remarked state, examining whether or not a value, expressing the originally remarked state, obtaining a value h=f(f(...f(P)...)), defining a value g(<

p,q>

,c) and storing the next state by changing the particular external input to one of external inputs until the next states g(<

p,q>

,c) for the originally remarked state <

p,q> and

all of the external inputs are defined and stored, and

cancelling the definition of the value f(<

p,q>

) of the failure function f for the originally remarked state <

p,q>

;

detecting means for detecting a plurality of types of features of a product at one time every prescribed time and outputting time-sequentially a string of inspecting values Iv, each of the inspecting values Iv indicating particular types of features of the product detected at one time;

control means for performing state-transitions of the finite-state machine with failure transitions transformed in the finite-state machine with failure transitions transforming means by utilizing the string of inspecting values Iv produced in the detecting means, each of the inspecting values Iv taking the finite-state machine with failure transitions from a current state s to a next state g(s,Iv) and an output μ

(s) being output from the next state g(s,Iv) in cases where a value g(s,Iv) of the success function g is defined, and each of the inspecting values Iv taking the finite-state machine with failure transitions from the current state s to a next state f(s) determined by a value f(s) of the failure function f in cases where the value g(s,Iv) of the success function g is not defined; and

action means for processing the product according to the outputs μ

(s) produced in the control means.

16. A system according to claim 15 in which the step of selecting an originally remarked state <

p,q>

in the finite-state machine with failure transitions transforming means includes the steps of;

judging whether or not a storage region Sr required to store values g(<

p,q>

,c) of the success function g defined in the finite-state machine with failure transitions and values f(<

p,q>

) of the failure function f defined in the finite-state machine with failure transitions is smaller than a fixed storage region; and

preparing the originally remarked state <

p,q>

on condition that the storage region Sr is smaller than the fixed storage region, and

the step of defining a value g(<

p,q>

,c) of the success function g includes the steps of;

judging whether or not an increased storage region required to additionally store the values g(<

p,q>

,c) of the success function g for the remarked state <

p,q> and

all of the external inputs c is smaller than the fixed storage region; and

defining the values g(<

p,q>

,c) of the success function g on condition that the increased storage region is equal to or smaller than the fixed storage region.

17. An automatic product inspection system, comprising:

finite-state machine with failure transitions transforming means for transforming, according to a transforming method, a finite-state machine with failure transitions in which the number of states <

p,q>

is finite, an external input c takes the finite-state machine with failure transitions from a current state s to a next state g(s,c) and an output μ

(s) is output from the next state g(s,c) in cases where a value g(s,c) of a success function g is defined, and an external input c takes the finite-state machine with failure transitions from the current state s to a next state g(h,c) (where h=f(f(...f(s)...))) determined by repeating a process that a value f(s) of the failure function f is calculated and the value f(s) is rewritten to the symbol s until a value g(h,c) of the success function g is defined in cases where a value g(s,c) of the success function g is not defined, the transforming method comprising the steps of

counting the number of state-transitions performed by applying the failure function f for each of current states and each of external inputs while operating the finite-state machine with failure transitions, the external inputs taking the finite-state machine with failure transitions from the current states to next states,

halting the operation of the finite-state machine with failure transitions in cases where the number of state-transitions from a particular current state <

p,q>

to a particular next state f(<

p,q>

) for a particular external input c reaches a fixed number of times, a state set p being defined as a non-empty subset of a finite state set Q of a nondeterministic finite-state machine, and a set r being defined as a subset of a finite state S of the finite-state machine with failure transitions,

expressing the particular current state <

p,q>

by a symbol P denoting a remarked state,

obtaining a value h=f(f(...f(P)...)) by repeating a process that a value f(P) of the failure function f for the remarked state P is calculated and the value f(P) is rewritten to the symbol P denoting a remarked state newly defined until a value g(h,c) of the success function g is defined in the finite-state machine with failure transitions,

defining a value g(<

p,q>

,c) of the success function g as g(h,c) to determine a next state g(<

p,q>

,c)=g(h,c) for the particular current state <

p,q> and

the particular external input c,

storing the next state g(<

p,q>

,c), and

restarting the operation of the finite-state machine with failure transitions;

detecting means for detecting a plurality of types of features of a product at one time every prescribed time and outputting time-sequentially a string of inspecting values Iv, each of the inspecting values Iv indicating particular types of features of the product detected at one time;

control means for performing state-transitions of the finite-state machine with failure transitions transformed in the finite-state machine with failure transitions transforming means by utilizing the string of inspecting values Iv produced in the detecting means, each of the inspecting values Iv taking the finite-state machine with failure transitions from a current state s to a next state g(s,Iv) and an output μ

(s) being output from the next state g(s,Iv) in cases where a value g(s,Iv) of tile success function g is defined, and each of the inspecting values Iv taking the finite-state machine with failure transitions from the current state s to a next state f(s) determined by a value f(s) of the failure function f in cases where the value g(s,Iv) of the success function g is not defined; and

action means for processing the product according to the outputs μ

(s) produced in the control means.

18. A document retrieving apparatus for collating strings of external characters written in an input document with one or more strings of referential characters and finding out one or more strings of external characters respectively agreeing with one of the strings of referential characters, comprising:

pattern matching machine constructing means for constructing a pattern matching machine from a nondeterministic finite-state machine according to a constructing method, the constructing method comprising the steps of

preparing the nondeterministic finite-state machine, an external input taking the nondeterministic finite-state machine from a current state to a plurality of next states,

producing a deterministic finite-state machine by utilizing the nondeterministic finite-state machine, an external character taking the deterministic finite-state machine from a current state to a next state and specifying an output at the next state, a form for specifying the next state and the output in the deterministic finite-state machine being the same as that in the nondeterministic finite-state machine or being expressed according to a pattern expression in which the form is equivalent to that in the nondeterministic finite-state machine and is convertible into that in the nondeterministic finite-state machine,

regarding a combination <

p,r>

of state sets p and r as states of the deterministic finite-state machine, the state set p being defined as a non-empty subset of a finite state set Q of the nondeterministic finite-state machine, and the state set r being defined as a subset of a finite state S of the deterministic finite-state machine,

setting an initial state s₀ of the deterministic finite-state machine to a state <

{q₀),s₀ >

, q₀ denoting an initial state of the nondeterministic finite-state machine,

storing the initial state s₀ =<

(q₀),s₀ >

to add the initial state s₀ to a state set of the deterministic finite-state machine as an element having an unprocessed tag,

setting an output μ

(s₀) of the deterministic finite-state machine at the initial state s₀ to be a set {λ

(q₀)} having an output of the nondeterministic finite-state machine at the initial state q₀,

storing the output μ

(s₀),

checking whether or not one or more elements respectively having an unprocessed tag exist in the state set of the deterministic finite-state machine,

selecting an element <

p,r>

first added to the state set of the deterministic finite-state machine from the state set of the deterministic finite-state machine as a selected element in cases where one or more elements <

p,r>

respectively having an unprocessed tag exist in the state set of the deterministic finite-state machine,

changing the selected element <

p,r>

having an unprocessed tag to an selected element <

p,r>

having a processed tag,

selecting the initial state s₀ as an element of a set x in case of <

p,r>

=s₀,

repeating a first calculation r(<

p,r>

) for taking out a second component r of the selected state <

p,r>

one or more times until values g(.,c)=g(r(r(...r(<

p,r>

)...)),c) of a success function g are defined to obtain a state u=r(r(...r(<

p,r>

)...)) and selecting values g(u,c) of the success function g for the state u and first referential characters c as values of a set x in case of <

p,r>

≠

s₀, the first referential characters c specifying a no-empty set of next states δ

(t,c) defined in the nondeterministic finite-state machine according to one of elements t of a state set p of the nondeterministic finite-state machine which corresponds to a first component of the selected state <

p,r>

,

calculating a first union Uδ

(t,c) of next states δ

(t,c) of the nondeterministic finite-state machine for elements t of the state set p and the first referential characters c;

calculating a second union p(x)Up(r(x))Up(r(r(x)))U--Up(r(r(...r(x)...))) of a string of sets p(x),p(r(x)),p(r(r(x))), - - - ,p(r(r(...r(x)...))) obtained by applying a second calculation for taking out a first component p of the selected state <

p,r>

of the deterministic finite-state machine after the first calculation r(x) is repeated a zero time or more,

selecting difference sets Uδ

(t,c)-p(x)Up(r(x))Up(r(r(x)))U--Up(r(r(...r(x)...))) of the first and second unions for the first referential characters c as values of a set y,

setting one or more values g(<

p,r>

,c) of the success function g for the selected element <

p,r>

denoting a current state and the first referential characters c to elements of the set x in cases where the set y is the empty set,

setting the values g(<

p,r>

,c) of the success function g to the states <

y,x>

in cases where the set y is not the empty set,

storing the values g(<

p,r>

,c) of the success function g to add the values g(<

p,r>

,c) to the state set of the deterministic finite-state machine as elements respectively having an unprocessed tag in cases where the values g(<

p,r>

,c) are not stored,

calculating a third union U{δ

(z,c)} of next states δ

(z,c) in the nondeterministic finite-state machine for elements z of a state set p of the nondeterministic finite-state machine corresponding to a first component of the selected element <

p,r> and

the first referential characters c,

setting output values μ

(g(<

p,r>

,c)) of an output function μ

of the deterministic finite-state machine at the states g(<

p,r>

,c) to a fourth union U{λ

(t)} of values λ

(t) of an output function λ

of the nondeterministic finite-state machine for elements t of the third union U{δ

(z,c)},

storing the output values μ

(g(<

p,r>

,c))=U{λ

(t)},

setting values f(g(<

p,r>

,c)) of the failure function f at the states g(<

p,r>

,c) to elements of a state set r of the nondeterministic finite-state machine corresponding to a second component of the selected element <

p,r>

in cases where one or more second referential characters c which specify next states δ

(t,c) defined in the nondeterministic finite-state machine according to one of elements t of a state set p of the nondeterministic finite-state machine corresponding to a first component of the selected element <

p,r>

exist,

storing the values f(g(<

p,r>

,c))=r,

repeating the steps of checking whether or not one or more elements, selecting an element <

p,r>

, changing the selected element, selecting the initial states, repeating a first calculation, calculating a first union, calculating a second union, selecting difference sets, setting one or more values, setting the values g(<

p,r>

,c), storing the values g(<

p,r>

,c), calculating a third union, setting output values, storing the output values, and setting values f(g(<

p,r>

,c)), storing the values f(g(<

p,r>

,c)) until no existence of an element having an unprocessed tag is detected in the step of checking whether or not one or more elements, and

defining the deterministic finite-state machine modified in the above steps as the pattern matching machine, wherein the number of states <

p,r>

is finite, a referential character c takes the pattern matching machine from a current state s to a next state g(s,c) and an output μ

(s) is output from the next state g(s,c) in cases where a value g(s,c) of the success function g is defined, and a referential character c takes the pattern matching machine from a current state s to a next state g(h,c) (where h=f(f(...f(s)...))) determined by repeating a process that a value f(s) of the failure function f is calculated and the value f(s) is rewritten to the symbol s until a value g(h,c) of the success function g is defined in cases where a value g(s,c) of the success function g is not defined;

input document storing means for storing a plurality of strings of external characters written in an input document and outputting time-sequentially remarked characters Cr selected from the external characters one by one;

success function storing means for storing values of the success function g defined in the pattern matching machine constructing means;

failure function storing means for storing values of the failure function g defined in the pattern matching machine constructing means;

state recording means for recording a particular state g(t1,Cr) denoting a next state in cases where a value g(t1,Cr) of the success function g for a current state t1 of the pattern matching machine and a remarked character Cr output from the input document storing means is defined in the success function storing means, and recording a particular state g(h,Cr) (where h=f(f(...f(t1)...))) as a next state determined by repeating a process that a value f(t1) of the failure function f is calculated and the value f(t1) is rewritten to the symbol t1 newly defined until a value g(h,Cr) of the success function defined is found out in the success function storing means in cases where a value g(t1,Cr) of the success function g for a current state t1 of the pattern matching machine and a remarked character Cr output from the input document storing means is not defined in the success function storing means; and

action storing means for storing actions denoting outputs at the states of the pattern matching machine produced in the pattern matching machine constructing means and outputting particular actions corresponding to particular states St time-sequentially transferred from the state recording means, the particular actions being used to judge whether or not a string of remarked characters Cr relating to the particular states St is pattern-matched with one of the strings of referential characters.

19. A document retrieving apparatus for collating strings of external characters written in an input document with one or more strings of referential characters and finding out one or more strings of external characters respectively agreeing with one of the strings of referential characters, comprising:

pattern matching machine transforming means for transforming, according to a transforming method, a pattern matching machine in which the number of states <

p,r>

is finite, a referential character c takes the pattern matching machine from a current state s to a next state g(s,c) and an output μ

(s) is output from the next state g(s,c) in cases where a value g(s,c) of a success function g is defined, and a referential character c takes the pattern matching machine from the current state s to a next state g(h,c) (where h=f(f(...f(s)...))) determined by repeating a process that a value f(s) of the failure function f is calculated and the value f(s) is rewritten to the symbol s until a value g(h,c) of the success function g is defined in cases where the value g(s,c) of the success function g is not defined, the transforming method comprising the steps of

selecting an originally remarked state <

p,r>

of the pattern matching machine and a particular referential character c, a state set p being defined as a non-empty subset of a finite state set Q of a nondeterministic finite-state machine, and a set r being defined as a subset of a finite state S of the pattern matching machine,

examining whether or not a value g(<

p,r>

, c) of the success function g for the originally remarked state <

p,r> and

the particular referential character c is defined,

expressing the originally remarked state <

p,r>

by a symbol P denoting a remarked state in cases where the value g(<

p,r>

,c) of the success function g is not defined,

obtaining a value h=f(f(...f(P)...)) by repeating a process that a value f(P) of the failure function f for the remarked state P is calculated and the value f(P) is rewritten to the symbol P denoting a remarked state newly defined until a value g(h,c) of the success function g is defined in the pattern matching machine,

defining a value g(<

p,r>

,c) of the success function g as g(h,c) to determine a next state g(<

p,r>

,c)=g(h,c) for the originally remarked state <

p,r> and

the particular referential character c,

storing the next state g(<

p,r>

,c),

repeating the above steps of selecting an originally remarked state, examining whether or not a value, expressing the originally remarked state, obtaining a value h=f(f(...f(P)...)), defining a value g(<

p,r>

,c) and storing the next state by changing the particular referential character to one of referential characters until the next states g(<

p,r>

,c) for the originally remarked state <

p,r> and

all of the referential characters are defined and stored, and

cancelling the definition of the value f(<

p,r>

) of the failure function f for the originally remarked state <

p,r>

;

input document storing means for storing a plurality of strings of external characters written in an input document and outputting time-sequentially remarked characters Cr selected from the external characters one by one;

success function storing means for storing values of the success function g defined in the pattern matching machine transforming means;

failure function storing means for storing values of the failure function g defined in the pattern matching machine transforming means;

state recording means for recording a particular state St=g(t1,Cr) denoting a next state in cases where a value g(t1,Cr) of the success function g for a current state t1 of the pattern matching machine and a remarked character Cr output from the input document storing means is defined in the success function storing means, and recording a particular state St=g(f(f(...f(t1)...)),Cr) denoting a next state in cases where a value g(t1,Cr) of the success function g for a current state t1 of the pattern matching machine and a remarked character Cr output from the input document storing means is not defined in the success function storing means, a value f(f(...f(t1)...)) being obtained by repeatedly finding out a value f(P) of the failure function g for a calculated result P while rewriting the value f(P) to the calculated result P in the failure function storing means until a value g(f(f(...f(t1)...)),Cr) of the success function g for the value f(f(...f(t1)...)) is found out in the success function storing means, and the value g(f(f(...f(t1)...)),Cr) found out in the success function storing means being transferred to the state recording means; and

action storing means for storing actions denoting outputs at the states of the pattern matching machine produced in the pattern matching machine constructing means and outputting particular actions corresponding to particular states St time-sequentially transferred from the state recording means, the particular actions being used to judge whether or not a string of remarked characters Cr relating to the particular states St is pattern-matched with one of the strings of referential characters.

20. A system according to claim 19 in which the step of selecting an originally remarked state <

p,r>

in the pattern matching machine transforming means includes the steps of;

judging whether or not a storage region Sr required to store values g(<

p,r>

,c) of the success function g defined in the pattern matching machine and values f(<

p,r>

) of the failure function f defined in the pattern matching machine is smaller than a fixed storage region; and

preparing the originally remarked state <

p,r>

on condition that the storage region Sr is smaller than the fixed storage region, and

the step of defining a value g(<

p,r>

,c) of the success function g includes the steps of;

judging whether or not an increased storage region required to additionally store the values g(<

p,r>

,c) of the success function g for the remarked state <

p,r> and

all of the referential characters c is smaller than the fixed storage region; and

defining the values g(<

p,r>

,c) of the success function g on condition that the increased storage region is equal to or smaller than the fixed storage region.

21. A document retrieving apparatus for collating strings of external characters written in an input document with one or more strings of referential characters and finding out one or more strings of external characters respectively agreeing with one of the strings of referential characters, comprising:

pattern matching machine transforming means for transforming, according to a transforming method, a pattern matching machine in which the number of states <

p,r>

is finite, a referential characters c takes the pattern matching machine from a current state s to a next state g(s,c) and an output μ

(s) is output from the next state g(s,c) in cases where a value g(s,c) of a success function g is defined, and a referential characters c takes the pattern matching machine from the current state s to a next state g(h,c) (where h=f(f(...f(s)...))) determined by repeating a process that a value f(s) of the failure function f is calculated and the value f(s) is rewritten to the symbol s until a value g(h,c) of the success function g is defined in cases where the value g(s,c) of the success function g is not defined, the transforming method comprising the steps of

counting the number of state-transitions performed by applying the failure function f for each of current states and each of referential characters while operating the pattern matching machine, the referential characters taking the pattern matching machine from the current states to next states,

halting the operation of the pattern matching machine in cases where the number of state-transitions from a particular current state <

p,r>

to a particular next state f(<

p,r>

) for a particular referential characters c reaches a fixed number of times, a state set p being defined as a non-empty subset of a finite state set Q of a nondeterministic finite-state machine, and a set r being defined as a subset of a finite state S of the pattern matching machine,

expressing the particular current state <

p,r>

by a symbol P denoting a remarked state,

obtaining a value h=f(f(...f(P)...)) by repeating a process that a value f(P) of the failure function f for the remarked state P is calculated and the value f(P) is rewritten to the symbol P denoting a remarked state newly defined until a value g(h,c) of the success function g is defined in the pattern matching machine,

defining a value g(<

p,r>

,c) of the success function g as g(h,c) to determine a next state g(<

p,r>

,c)=g(h,c) for the particular current state <

p,r> and

the particular referential characters c,

storing the next state g(<

p,r>

,c), and

restarting the operation of the pattern matching machine;

input document storing means for storing a plurality of strings of external characters written in an input document and outputting time-sequentially remarked characters Cr selected from the external characters one by one;

success function storing means for storing values of the success function g defined in the pattern matching machine transforming means;

failure function storing means for storing values of the failure function g defined in the pattern matching machine transforming means;

state recording means for recording a particular state St=g(t1,Cr) denoting a next state in cases where a value g(t1,Cr) of the success function g for a current state t1 of the pattern matching machine and a remarked character Cr output from the input document storing means is defined in the success function storing means, and recording a particular state St=g(f(f(...f(t1)...)),Cr) denoting a next state in cases where a value g(t1,Cr) of the success function g for a current state t1 of the pattern matching machine and a remarked character Cr output from the input document storing means is not defined in the success function storing means, a value f(f(...f(t1)...)) being obtained by repeatedly finding out a value f(P) of the failure function g for a calculated result P while rewriting the value f(P) to the calculated result P in the failure function storing means until a value g(f(f(...f(t1)...)),Cr) of the success function g for the value f(f.(...f(t1)...)) is found out in the success function storing means, and the value g(f(f(...f(t1)...)),Cr) found out in the success function storing means being transferred to the state recording means; and

action storing means for storing actions denoting outputs at the states of the pattern matching machine produced in the pattern matching machine constructing means and outputting particular actions corresponding to particular states St time-sequentially transferred from the state recording means, the particular actions being used to judge whether or not a string of remarked characters Cr relating to the particular states St is pattern-matched with one of the strings of referential characters.