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

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 .mu.(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>.

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 .mu.(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.

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.sub.0 of the deterministic finite-state machine to a state <{q.sub.0),s.sub.0 >, q.sub.0 denoting an initial state of the nondeterministic finite-state machine;
• storing the initial state s.sub.0 =<{q.sub.0 },s.sub.0 >
• to add the initial state s.sub.0 to a state set of the deterministic finite-state machine as an element having an unprocessed tag;
• setting an output .mu.(s.sub.0) of the deterministic finite-state machine at the initial state s.sub.0 to be a set {.lambda.(q.sub.0)} having an output of the nondeterministic finite-state machine at the initial state q.sub.0 ;
• storing the output .mu.(s.sub.0);
• 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.sub.0 as an element of a set x in case of <p,r>=s.sub.0 ;
• 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>.noteq.s.sub.0, the first referential characters c specifying a no-empty set of next states .delta.(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.delta.(t,c) of next states .delta.(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.delta.(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{.delta.(z,c)} of next states .delta.(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 .mu.(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{.lambda.(t)} of values .lambda.(t) of an output function .lambda. of the nondeterministic finite-state machine for elements t of the third union U{.delta.(z,c)};
• storing the output values .mu.(g(<p,r>,c))=U{.lambda.(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 .delta.(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 .mu.(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.

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 .mu.(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>.

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 .mu.(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.

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.sub.0 of the deterministic finite-state machine to a state <{q.sub.0 },{q.sub.0 }>, q.sub.0 denoting an initial state of the nondeterministic finite-state machine,
• storing the initial state s.sub.0 =<{q.sub.0),{q.sub.0)>
• to add the initial state s.sub.0 to a state set of the deterministic finite-state machine as an element having an unprocessed tag,
• setting an output .mu.(s.sub.0) of the deterministic finite-state machine at the initial state s.sub.0 to be a set {.lambda.(q.sub.0)) having an output of the nondeterministic finite-state machine at the initial state q.sub.0,
• storing the output .mu.(s.sub.0),
• producing a state <.phi.,.phi.>
• of the deterministic finite-state machine obtained in case of q=.phi.,
• storing the state <.phi.,.phi.>
• to add the state <.phi.,.phi.>
• to the state set of the deterministic finite-state machine as an element having a processed tag,
• setting a value .mu.(<.phi.,.phi.>) of an output function .mu. of the deterministic finite-state machine at the state <.phi.,.phi.>
• to be an empty set .phi.,
• storing the value .mu.(<.phi.,.phi.>),
• setting values g(<.phi.,.phi.>,c) of a success function g for arbitrary external inputs c to be the state <.phi.,.phi.>,
• storing the values g(<.phi.,.phi.>,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 .delta.(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.delta.(t,c) of the next states .delta.(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{.lambda.(t)} of outputs .lambda.(t) of the nondeterministic finite-state machine for elements t of the set y as output values .mu.(<x,y>) of the output function .mu. of the deterministic finite-state machine at the states <x,y>
• in cases where the values .mu.(<x,y>) are not defined,
• storing the output values .mu.(<x,y>)=U{.lambda.(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{.lambda.(t)} of outputs .lambda.(t) of the nondeterministic finite-state machine for elements t of the difference set q-p to output values .mu.(<z,q-p>) of the output function .mu. of the deterministic finite-state machine at the states <z,q-p>
• in cases where the values .mu.(<x,y>) of the output function .mu. are not defined,
• storing the output values .mu.(<z,q-p>)=U{.lambda.(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.delta.(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{.lambda.(t)}, storing the output values .mu.(<x,y>), setting values f(<p,q>), storing the values f(<p,q>), setting a union U{.lambda.(t)}, and storing the output values .mu.(<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 .mu.(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 .mu.(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 .mu.(s) produced in the control means.

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 .mu.(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 .mu.(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 .mu.(s) produced in the control means.

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 .mu.(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 .mu.(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 .mu.(s) produced in the control means.

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.sub.0 of the deterministic finite-state machine to a state <{q.sub.0),s.sub.0 >, q.sub.0 denoting an initial state of the nondeterministic finite-state machine,
• storing the initial state s.sub.0 =<(q.sub.0),s.sub.0 >
• to add the initial state s.sub.0 to a state set of the deterministic finite-state machine as an element having an unprocessed tag,
• setting an output .mu.(s.sub.0) of the deterministic finite-state machine at the initial state s.sub.0 to be a set {.lambda.(q.sub.0)} having an output of the nondeterministic finite-state machine at the initial state q.sub.0,
• storing the output .mu.(s.sub.0),
• 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.sub.0 as an element of a set x in case of <p,r>=s.sub.0,
• 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>
• .noteq.s.sub.0, the first referential characters c specifying a no-empty set of next states .delta.(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.delta.(t,c) of next states .delta.(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.delta.(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{.delta.(z,c)} of next states .delta.(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 .mu.(g(<p,r>,c)) of an output function .mu. of the deterministic finite-state machine at the states g(<p,r>,c) to a fourth union U{.lambda.(t)} of values .lambda.(t) of an output function .lambda. of the nondeterministic finite-state machine for elements t of the third union U{.delta.(z,c)},
• storing the output values .mu.(g(<p,r>,c))=U{.lambda.(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 .delta.(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 .mu.(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.

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 .mu.(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.

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 .mu.(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.