Constructing method of finite-state machine performing transitio

Details Constructing method of finite-state machine performing transitio Constructing method of finite-state machine performing transitio

1994-10-28

1996-02-27

Ruggiero, Joseph

Boots, shoes, and leggings

36441919, 36455101, 395600, G06F 1710, G06F 1900

Patent

active

054954096

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

REFERENCES:
patent: 4799141 (1989-01-01), Drusinsky et al.
patent: 4985863 (1991-01-01), Fujisawa et al.
patent: 5051886 (1991-09-01), Kawaguchi et al.
patent: 5163016 (1992-11-01), Har'El
patent: 5265242 (1993-11-01), Fujisawa et al.
patent: 5278981 (1994-01-01), Kawaguchi et al.
patent: 5388234 (1995-02-01), Kanno et al.
patent: 5406480 (1995-04-01), Kanno
Computation: Finite and Infinite Machines; by Minsky: 1967.
"Regular Expressions and State Graphs for Automata" by McNaughton et al; 1960.
"Automata and Theory of Languages", E. Tomita et al., Morikita Press; May 1992.
"Theory of Automata", Arto Salomaa, Pergamon Press, 1969.
"Theory of Automata", Toshio Kitagawa et al., 1974, Kyoritsu Press.
"Formal Languages and Their Relation to Automata", John Hopcroft et al., 1964.
"Language Theory and Automa", translated by Akihiro Nozaki et al., Science Inc., 1971.
"Fast Pattern Matching in Strings", Donald Knuth et al., Siam J. Comput., vol. 6, No. 2, Jun. 1977.
"High Speed Pattern Matching Algorithm for Processing All Sentences of a Text", Masayuki Takeda, 1991 Information Study Symposium.

Affiliated with

Also associated with

Rating

Constructing method of finite-state machine performing transitio does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Constructing method of finite-state machine performing transitio, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constructing method of finite-state machine performing transitio will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1683601