Nondeterministic FSMs in hardware?
Reetinder P. S. Sidhu
Hi all
I'm a PhD student whose current research focuses on nondeterministic
FSMs. It seems to me that there are interesting ways of implementing
them efficiently in hardware. I was wondering if nondeterministic FSMs
have previously been implemented in VLSI/programmable logic and if so,
for what applications.
I would be grateful for any info/pointers regarding above. Thanks in
advance.
Regards
Eric C. Fromm
and I would be grateful if someone would simply explain what these things
are...
i.e., in what sense deterministic?
thanks,
-eric
--
Eric C. Fromm efr...@sgi.com
Principal Engineer Scalable Systems Division
SGI - Silicon Graphics, Inc. Chippewa Falls, Wi.
George Coulouris
Given a state and an input symbol, a deterministic finite automaton (DFA)
can "go to" only one next state. A nondeterministic finite state automaton
(NFA), however, may have multiple candidates for the next state.
DFAs and NFAs have equivalent expressive power, namely, that of the regular
expressions.
--
George Coulouris - http://www.tc.cornell.edu/~glc5/
Peter Alfke
tell us more about non-deterministic finite state machines.
What makes them non-deterministic?
Do they roll dice? ;-)
What's good about them?
Peter Alfke, Xilinx
==============================
"Reetinder P. S. Sidhu" wrote:
Eric C. Fromm
>
> Given a state and an input symbol, a deterministic finite automaton (DFA)
> can "go to" only one next state. A nondeterministic finite state automaton
> (NFA), however, may have multiple candidates for the next state.
>
> DFAs and NFAs have equivalent expressive power, namely, that of the regular
> expressions.
>
> --
> George Coulouris - http://www.tc.cornell.edu/~glc5/
OK, I get the 'multiple candidates for next state' bit. You lost me with
the 'expressive power' assertion though. What is this characteristic and
how do DFAs and NFAs compare to other constructs (and what are those
constructs)?
Pete Smoot
> OK, I get the 'multiple candidates for next state' bit. You lost me with
> the 'expressive power' assertion though. What is this characteristic and
> how do DFAs and NFAs compare to other constructs (and what are those
> constructs)?
If I recall my computability class from eons ago, I believe given a
NFA, you can construct an equivalent DFA. Basically, the states of
the DFA map to the sets of possible states the DFA could be in.
In other words, if from state A, event 1 could take it to either
states B or C, the DFA will have a state indicating the NFA is in
either state B or C.
-- Pete Smoot
Greg Neff
I did a search on Northern Light, and came up with some links,
including these:
http://www.cse.msu.edu/~torng/360Book/NFA/
http://www.netaxs.com/people/nerp/automata/nfa1.html
http://www.grappa.univ-lille3.fr/tata/
The first link refers to the NFA as an "unrealistic model of
computation". From a theoretical perspective, it's easy to follow how
an NFA works. I don't see how you would implement this in an FPGA,
without having a random number generator to produce "non-deterministic"
branches. So then, the NFA would be implemented as an FSA with a
random number generator output being used as an input to the state
machine. I can't imagine why anyone would want to do this for a
practical application, so I am also interested to see where the OP is
going with this.
--
Greg Neff
VP Engineering
*Microsym* Computers Inc.
gr...@guesswhichwordgoeshere.com
Sent via Deja.com
http://www.deja.com/
Paul DeMone
"Reetinder P. S. Sidhu" wrote:
>
What exactly do you mean? An FSM with probablistic state transitions
governed by a pseudo random sequence generator like an LFSR or a linear
congruence modulo multiplier? Or governed by a truely random noise
source like amplified thermal background noise?
--
Paul W. DeMone The 801 experiment SPARCed an ARMs race of EPIC
Kanata, Ontario proportions to put more PRECISION and POWER into
dem...@mosaid.com architectures with MIPSed results but ALPHA's well
pde...@igs.net that ends well.
Thomas Maslen
Rather too often.
Thomas Maslen
mas...@pobox.com
(Oh, you meant deliberately?)
Mark W Brehob
> Hi all
Humm, A "true" nondeterministic FSA, in the theoritical computer-science
sense would be novel, but I would think impossible to do "efficently." (At
least without some type of quantum trick.) If you have a way that really
does that I would be quite interested. It certainly would have significant
applications...
If you mean a FSM which randomly goes to different states based on certain
probabilities, I really have no clue if it has been done, nor do any
applications jump out at me. (But I'd not be shocked if there were many,
even in computer architecture.)
Mark
> Regards
--
~~~~~~~~~~~~~~~~ http://www.cps.msu.edu/~brehob ~~~~~~~~~~~~~~~~~~
~~~~~~Mark Brehob: Ultimate Player, Gamer, Computer Geek~~~~~~~~~~
Philip Freidin
-- philip
On 4 Jan 2001 13:59:30 -0800, si...@halcyon.usc.edu (Reetinder P. S. Sidhu)
wrote:
Philip Freidin
Fliptronics
del cecchi
Tell us more.
del cecchi
"Reetinder P. S. Sidhu" <si...@halcyon.usc.edu> wrote in message
news:932ro2$j6e$1...@halcyon.usc.edu...
amoli...@visi-dot-com.com
>What exactly do you mean? An FSM with probablistic state transitions
>governed by a pseudo random sequence generator like an LFSR or a linear
>congruence modulo multiplier? Or governed by a truely random noise
>source like amplified thermal background noise?
_Compilers:_Principles,_Techniques,_and_Tools_
discusses this. What you do with an NFA is that you essentially
"take" all the transitions that are possible in a state,
at once.
Your current "state" is really the set of all the states
of the NFA (Non-deterministic Finite Automaton) that you could
be in. You take all the possible transitions out of all those
states that you could be in. I think if one of the new
states is a terminating state, you stop.
You can implement these things pretty efficiently (for
a fixed maximum number of states) by managing your current state
as a bit-vector which indicates which of the NFA states you
are currently in.
You should be able to, um, use the current bit vector as
enables on a set of functional units (one per state) each of
which consumes the current input symbol and emits a new
bit vector of possible states. Then OR the results of all
the functional units together to get your new state. And the
current state vector with a vector representing terminating
states, if the result is non-zero, stop.
Your hardware will set a Really Hard cap on the maximum
number of NFA states you support. The details of how input symbols
select transitions will determine the inner structure of the
functional units. If, for eaxmple, you are doing string matching,
there is a straightforward way to convert a regular expression into an
NFA. If you support up to, say, 64 states (which will capture regular
expressions up to something near 64 characters long, I think), each
state (functional unit) can be a 256 element memory 64 bits wide. The
input symbol is a character, and acts as the address. Address all
the little RAMs at once, and use the current input state as output
enables on the RAMs. This could go quite fast, though where you'd
find RAMs that shape I have no idea. I guess you could do this in
an FPGA and do regexp matching at 100M characters/second? Network
Intrusion Detection, anyone?
Why I don't get is what makes this interesting,
it all seems pretty trivial to me. Am I missing something?
A previous poster basically summed it up. You implement
an NFA as a DFA (Deterministic Finite Automaton) whose states are
collections of the NFA state. The point of doing it as an NFA is
that you don't have to construct the entire DFA, you essentially
"dynamically" construct that states and transitions of an equivalent
DFA as you go. The NFA is generally quite a bit smaller than equivalent
DFAs (I think one can construct examples where equivalent DFAs all have
2^n states). Furthermore, if you need to run a finite automaton on one
input only, it is more efficient to run the NFA and (inefficiently)
construct only the DFA states you NEED instead of constructing the
entire DFA.
The referenced book has a nice discussion of many of these issues.
[ by the way, I forget, or never knew, whether one NFA can have
more than one equivalent DFA. I used the plural above, because
it feels right, but there may always be one DFA ]
Joe Pfeiffer
> the 'expressive power' assertion though. What is this characteristic and
> how do DFAs and NFAs compare to other constructs (and what are those
> constructs)?
Wow -- the best answer to that question is probably to take a class in
formal language theory... but here's a capsule summary.
There is a standard way of describing the complexity of a program's
inputs in terms of the features needed in the program to be able to
tell whether the program can tell whether or not an input is valid.
The set of valid inputs for a program is called a language, in analogy
to a natural language (like English) or a programming language.
You can describe this in terms of the class of language, the features
allowed in a grammar for the language, and the features required in a
machine that can recognise the language.
The hierarchy of languages is called the Chomsky hierarchy. Some of
the members are:
Variable names can be described by regular expressions, generated by
regular grammars, and recognized by finite state machines. You can
program one by using an enumerated type called a State, that keeps
track of where you are in the string you're trying to recognize. A
FSM would be able to tell if its input was a bunch of left and right
parentheses, but couldn't tell (in general) if they balanced -- if
your state variable had 100 states to count how many more left parens
you've seen that right parens, I could start my string with 101 left
parens and it would lose count. A compiler's lexical analyzer can
recognize regular expressions.
Arithmetic expressions can be generated by context free grammars and
recognized by pushdown automata (PDA) -- basically, finite state machines
with the addition of being able to push things on a stack, and pop
them off the stack. The stack can get infinitely deep (this is
theory, after all). Now we can tell if we have balanced parens:
every time you give me a left paren, I push it on the stack; every
time you give me a right paren I pop the stack. If I ever try to pop
an empty stack I've seen too many right parens; if there's anything
left on the stack at the end there were too many left parens.
Pushdown automata are interesting in that they can recognize more
languages if they can take guesses. So, if I want to recognize
palindromes with a deterministic (ie no guessing) PDA, I can only do
it if i've got a distinguished character that only appears at the
center of the palindrome -- in this case, I can push everything I see
until I hit the center, then pop everything after that. If what I pop
matches what I see all the way to the end, I've got a palindrome.
Now, if I've got a nondeterministic PDA I can just guess when to start
popping (it's guaranteed to make the right guess if there is a right
guess to be made). That's what makes the equivalence of deterministic
and nondeterministic FSMs counterintuitive: you'd think being able to
guess would make it more powerful in the sense that nPDAs are more
powerful than dPDAs, but it doesn't matter.
The parser in a compiler implements a PDA (that's not quite true, but
it'll pass in this discussion).
Turing Machines are the most powerful machines in the hierarchy; they
act like computers with infinite memory (the access to the memory is
very primitive, but that's a detail we don't need to worry about
here). One interesting thing about TMs is that it's possible to have
a langauge, and a string, and not be able to determine whether the
string is in the language or not! Even stranger, there are languages
for which we can tell if a string is in the langauge, but not
necessarily whether it's not; languages for which we can tell that a
string is definitely not in the language, but we can't tell for sure
whether it is; and (thankfully) languages for which can in fact tell
for sure. The Halting Problem is actually an example of a language
for which we can tell if a string is in the language but can't tell if
it isn't: let the language in question be ``the set of all programs
written in C that take no input.'' We can always tell if a program
halts: just watch and see what happens. We can sometimes tell if a
program doesn't halt (hmmmm, the first executable line is while(1);).
But there are C programs that we just can't tell for sure whether they
will ever halt (there's nothing in there that we can look at and tell
whether it's going to halt, and it's been running for three years now
without halting.... but is it really in a hard loop, or is it going
to terminate Real Soon Now?).
--
Joseph J. Pfeiffer, Jr., Ph.D. Phone -- (505) 646-1605
Department of Computer Science FAX -- (505) 646-1002
New Mexico State University http://www.cs.nmsu.edu/~pfeiffer
VL 2000 Homepage: http://www.cs.orst.edu/~burnett/vl2000/
Jan Gray
news:932ro2$j6e$1...@halcyon.usc.edu...
> FSMs. It seems to me that there are interesting ways of implementing
> them efficiently in hardware. I was wondering if nondeterministic FSMs
> have previously been implemented in VLSI/programmable logic and if so,
> for what applications.
[NFA=nondeterministic finite state automaton / FSM
DFA=deterministic finite state automaton / FSM]
Perhaps someday when/if we have quantum computing machines, we can build
NFAs directly, using qubit-tuples to represent states. But that is rather
far off.
To implement an NFA in hardware today, you could convert it to a DFA using
the subset construction, that is, you build an equivalent DFA whose states
are those subsets of the set of states of the NFA that are reachable by a
given input sequence (and any number of epsilon-transitions). See e.g.
Compilers: Principles, Techniques, and Tools, Aho, Sethi, Ullman,
pp.117-121, or the google-identified lecture notes that start at
http://tina.lancs.ac.uk/computing/courses/year2/230/233/L3/sld025.htm.
See also my note on Regular Expressions and Parsing in FPGAs, at
www.fpgacpu.org/usenet/re.html.
Jan Gray, Gray Research LLC
FPGA CPU News: www.fpgacpu.org
Terje Mathisen
>
> "Eric C. Fromm" <efr...@sgi.com> writes:
> >
> > OK, I get the 'multiple candidates for next state' bit. You lost me with
> > the 'expressive power' assertion though. What is this characteristic and
> > how do DFAs and NFAs compare to other constructs (and what are those
> > constructs)?
>
> Wow -- the best answer to that question is probably to take a class in
> formal language theory... but here's a capsule summary.
I nominate this as 'c.a Post of the Month'.
Very nice, Joe!
Terje
--
- <Terje.M...@hda.hydro.com>
Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"
Dennis O'Connor
> "Reetinder P. S. Sidhu" wrote:
> >
> > Hi all
> >
> > I'm a PhD student whose current research focuses on nondeterministic
> > FSMs. It seems to me that there are interesting ways of implementing
> > them efficiently in hardware. I was wondering if nondeterministic FSMs
> > have previously been implemented in VLSI/programmable logic and if so,
> > for what applications.
> >
> > I would be grateful for any info/pointers regarding above. Thanks in
> > advance.
>
> What exactly do you mean? An FSM with probablistic state transitions
> governed by a pseudo random sequence generator like an LFSR or a linear
> congruence modulo multiplier? Or governed by a truely random noise
> source like amplified thermal background noise?
"Nondeterministic" has nothing to do with randomness.
A "Nondeterminsitic Finite State Machine" would not chose which
transition out of a state it would take: it takes all of them : that's
the "nondeterminstic" part of it.
The reason such a machine is interesting is because it
can solve O(NP) problems in polynomial-bounded time.
However, the amount of hardware it takes to do so is
pretty large.
IIRC, determining whether a proposed solution to an O(NP)
problem actually does solve it is a O(P) problem. That is.
a deterministic FSM can test in polynomial-bounded
time whether a particular proposal solves an NP problem .
Therefor, one direct way to build the equivalent of a
nondeterminstic FSM is to build one deterministic FSM
(and we all know how to do that :) for each possible solution
to the NP problem, each of which checks whether its
solution is a correct one, and operate them all in parallel.
If the domain of possible solutions is finite and small enough,
this isn't entirely impractical, and since all the FSMs are
identical except for the solution they are testing,
designing such hardware would be straightforward.
I imagine there might be some interesting problems
where the hardware to do this might be justified by
the increase in speed, and especially be the increase
in worst-case time-to-solution.
--
Dennis O'Connor dm...@primenet.com
Vanity Web Page: http://www.primenet.com/~dmoc/
Lars Henrik Mathiesen
> [ by the way, I forget, or never knew, whether one NFA can have
> more than one equivalent DFA. I used the plural above, because
> it feels right, but there may always be one DFA ]
In general, both NFAs and DFAs can have redundant states, i.e., states
where the eventual outcome will be the same for any subsequent output
they are given.
In both cases, AFAIR, there are algorithms to reduce an automaton to
the smallest possible number of states, and I think those minimal
automata are unique. Authoritative answers in the dragon book, I'm
sure.
However, using a minimal NFA does not guarantee that the subset
algorithm alone will produce a minimal DFA.
Also, all of the above only applies as is to automata where you run
the whole input through and see if you end up in a success state.
Regular expressions are often unanchored at the right, and if you want
a matcher that stops as soon as it has a match, there's a few tricks
you have to use.
Lars Mathiesen (U of Copenhagen CS Dep) <tho...@diku.dk> (Humour NOT marked)
Torben AEgidius Mogensen
>amoli...@visi-dot-com.com writes:
>> [ by the way, I forget, or never knew, whether one NFA can have
>> more than one equivalent DFA. I used the plural above, because
>> it feels right, but there may always be one DFA ]
>In general, both NFAs and DFAs can have redundant states, i.e., states
>where the eventual outcome will be the same for any subsequent output
>they are given.
>In both cases, AFAIR, there are algorithms to reduce an automaton to
>the smallest possible number of states, and I think those minimal
>automata are unique.
Minimal DFA's are unique, minimal NFA's are not.
>However, using a minimal NFA does not guarantee that the subset
>algorithm alone will produce a minimal DFA.
Indeed. And minimizing an NFA has higher complexity than minimizing a
DFA, so there is little point in doing this first.
>Also, all of the above only applies as is to automata where you run
>the whole input through and see if you end up in a success state.
>Regular expressions are often unanchored at the right, and if you want
>a matcher that stops as soon as it has a match, there's a few tricks
>you have to use.
Most applications want the longest matching prefix of a string, not
the shortest.
Torben Mogensen (tor...@diku.dk)
Jean-Marc Bourguet
I wonder what precisely do you call non determinitic FSMs. I see at
least 3 meanings for it:
- something like what is used in the building of scanner which can
also be described as a FSM having several active states at one
moment where all possible state transition are taken at a given
time;
- something like Petri nets which, if memory serve, can also be
described as a FSM having several active states at one moment;
one arbitrary possible transition is taken at a given time; one
transition desactivate one state and activate one or more new
states (if they where not alreay activated obviously);
- a FSM having one active state where one random possible state
transition is taken.
The first two may also be described as a deterministic FSM and I see
little interest of implementing then in an other way in VLSI. Wait,
it is the other way: deterministic FSM are implemented as non
deterministic FSM in the first meaning (every flip flop correspond
to a state, all possible transitions are always taken) :-) What I want
to say is that all these kind of machines are different descriptions
for the same reality. If you have have not seen this, I wonder if your
way of implementing them are really interestingly efficient (perhaps if
you consider other constraints that the classical one, but then it is
more the constraints that are interesting than the solution).
I know of nothing about implementing the third meaning. I currently
fail to see an application as well as an efficient implementation in
VLSI.
-- Jean-Marc
Eric C. Fromm
>
> Joe Pfeiffer wrote:
> >
> > "Eric C. Fromm" <efr...@sgi.com> writes:
> > >
> > > OK, I get the 'multiple candidates for next state' bit. You lost me with
> > > the 'expressive power' assertion though. What is this characteristic and
> > > how do DFAs and NFAs compare to other constructs (and what are those
> > > constructs)?
> >
> > Wow -- the best answer to that question is probably to take a class in
> > formal language theory... but here's a capsule summary.
>
> I nominate this as 'c.a Post of the Month'.
>
> Very nice, Joe!
>
> Terje
My sentiments exactly.
Del Cecchi
Yes, quite informative (what I understood of it), but disappointing. I thought we
would get to make state machines with little white noise generators in them to
aid in the control of the state transitions. :-)
--
Del Cecchi
cecchi@rchland
Greg Neff
"Dennis O'Connor" <dm...@primenet.com> wrote:
(snip)
>
> "Nondeterministic" has nothing to do with randomness.
>
> A "Nondeterminsitic Finite State Machine" would not chose which
> transition out of a state it would take: it takes all of them : that's
> the "nondeterminstic" part of it.
>
The information that I found on the WWW indicates that only one of the
branches is taken, not all of them at the same time. If it took all of
the possible branches at the same time, then it would be deterministic,
and would end up in multiple states simultaneously. I thought that
each NFA set description in the configuration sequence indicates the
set of possible states (only one of which is active) at that point in
time.
--
Greg Neff
VP Engineering
*Microsym* Computers Inc.
gr...@guesswhichwordgoeshere.com
George Coulouris
>In article <933shl$1h5a$1...@node17.cwnet.frontiernet.net>,
> "Dennis O'Connor" <dm...@primenet.com> wrote:
>(snip)
>>
>> "Nondeterministic" has nothing to do with randomness.
>>
>> A "Nondeterminsitic Finite State Machine" would not chose which
>> transition out of a state it would take: it takes all of them : that's
>> the "nondeterminstic" part of it.
>>
>(snip)
>
>The information that I found on the WWW indicates that only one of the
>branches is taken, not all of them at the same time. If it took all of
>the possible branches at the same time, then it would be deterministic,
>and would end up in multiple states simultaneously. I thought that
>each NFA set description in the configuration sequence indicates the
>set of possible states (only one of which is active) at that point in
>time.
If any path puts the NFA in a final state, the input string is accepted.
You can visualize this as the NFA taking all paths simultaneously, or as the
NFA "choosing" the "right" path nondeterministically.
"It's only a model" -- Patsy
Greg Pfister
Right. That property lets you create machines that accept certain
classes of input strings (languages) with fewer states than
normal deterministic FSMs, and possibly, I forget, creat machines
that accept languages that deterministic FSMs can't distinguish.
Now, will somebody please explain to me why NFSMs are worth
talking about? I learned about and taught this gorp back in the
late 60s. (I certainly wouldn't waste time doing so now.) It was
sort of cute theory, not much content that I oculd see, with
little to recommend it in practice. Can't say that I see much
difference now, and there are lots more interesting things to
talk about.
Greg Pfister
<not my employer's opinion>
Greg Neff
gl...@cornell.edu wrote:
(snip)
>
> If any path puts the NFA in a final state, the input string is
accepted.
> You can visualize this as the NFA taking all paths simultaneously, or
as the
> NFA "choosing" the "right" path nondeterministically.
>
Okay, so if I had to implement this in hardware (as requested by the OP)
then I can see two different approaches:
1) Follow all paths simultaneously. This is completely deterministic
from an implementation perspective. In this case, multiple states can
be active at the same time, and the final state *will* be active if the
input string is acceptable. From a hardware perspective this is
trivial, so I don't know why the OP would need assistance in
implementing this.
2) Non-deterministically pick one path when more than one path is
possible from each state. In this case, only one state will be active
at any given point in time, and the final state *may* be active if the
input string is acceptable. I'm thinking that this is what the OP was
asking about, but I'm not sure.
Kelly Hall
> Right. That property lets you create machines that accept certain
> classes of input strings (languages) with fewer states than
> normal deterministic FSMs, and possibly, I forget, creat machines
> that accept languages that deterministic FSMs can't distinguish.
>
> Now, will somebody please explain to me why NFSMs are worth
> talking about? I learned about and taught this gorp back in the
> late 60s. (I certainly wouldn't waste time doing so now.) It was
> sort of cute theory, not much content that I oculd see, with
> little to recommend it in practice. Can't say that I see much
> difference now, and there are lots more interesting things to
> talk about.
I'm not Mr. Hardware, but it occurs to me that there might be some use
for networking gear - switches, routers, maybe firewalls. If I can
add new MACs or IPs to a NFA instead of a flat table that I have to
iterate through, it could be a speedup. Maybe CAMs make this moot,
though.
Kelly
Bernd Paysan
> Yes, quite informative (what I understood of it), but disappointing. I thought we
> would get to make state machines with little white noise generators in them to
> aid in the control of the state transitions. :-)
You could synthesize the NFA, and use Q-bits instead of flip-flops to
hold the states. According to the theory of quantum computers, you
should have an efficient hardware implementation of a NFA (i.e. you need
just log2(n) Q-bits, even if the corresponding DFA requires 2^n states,
and therefore at least n Flip-Flops).
The labs at IBM seem to have produced some Q-bits lately.
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://www.jwdt.com/~paysan/
Joe Pfeiffer
> Now, will somebody please explain to me why NFSMs are worth
> talking about? I learned about and taught this gorp back in the
> late 60s. (I certainly wouldn't waste time doing so now.) It was
> sort of cute theory, not much content that I oculd see, with
> little to recommend it in practice. Can't say that I see much
> difference now, and there are lots more interesting things to
> talk about.
Because regular expressions are (most of the time) the most
straightforward way of describing the set you want to recognize
(assuming a FSM can do it at all), and REs translate easily to NFSMs.
Then you use a NFSM -> DFSM construction to get something executable.
Also, of coures, it's intuitively obvious that NFSMs *have* to be more
powerful than DFSMs, so the fact that the construction is so easy
makes a good warmup for hitting the same fact later in Turing
Machines.
Joe Pfeiffer
> Okay, so if I had to implement this in hardware (as requested by the OP)
> then I can see two different approaches:
>
> 1) Follow all paths simultaneously. This is completely deterministic
> from an implementation perspective. In this case, multiple states can
> be active at the same time, and the final state *will* be active if the
> input string is acceptable. From a hardware perspective this is
> trivial, so I don't know why the OP would need assistance in
> implementing this.
This has to be what he meant. The thing is, a naive translation from
NFSM to DFSM takes 2^N states, where N is the number of states in the
NFSM. There are ways to reduce the number of states, but I don't know
if there is any sort of proved optimum, in general. The OP's point
was that he was looking for efficient representation.
>
> 2) Non-deterministically pick one path when more than one path is
> possible from each state. In this case, only one state will be active
> at any given point in time, and the final state *may* be active if the
> input string is acceptable. I'm thinking that this is what the OP was
> asking about, but I'm not sure.
Unless the OP is using words in nonstandard ways, this just isn't
possible. You see, it's not just that the automaton makes a choice,
it always makes the *right* choice, based on information it doesn't
have yet. Can't do that, sorry!
Jonathan Thornburg
Greg Pfister <pfi...@us.ibm.com> wrote:
>Now, will somebody please explain to me why NFSMs are worth
>talking about? I learned about and taught this gorp back in the
>late 60s. (I certainly wouldn't waste time doing so now.) It was
>sort of cute theory, not much content that I oculd see, with
>little to recommend it in practice. Can't say that I see much
>difference now, and there are lots more interesting things to
>talk about.
If you're a hardware person, DFSMs are all over the place, eg
multiprocessor cache protocols, hardware cache/TLB refills, or for that
matter hardwired within-an-instruction sequencing logic (the sort that
might otherwise be done by microcode). I don't know for sure, but
perhaps NFSMs might come in handy for investigating or reasoning about
the set of all reachable states of a DFSM for design-validation purposes?
If you're a software person, think of an NFSM as one way of implementing
regular expressions (regexps)... which are the essence of egrep(1) and
kindred programs, and are very important components of Perl, the more
powerful command-line shells, all Real Programmer's Editors, and assorted
other software which escapes my mind at the moment.
There's a considerable (abeit rather scattered) literature on implementing
regexps, with several good freeware packages, occasional usenet flamefests
on which is "better" (faster, less buggy, ...). POSIX 1003.2 defines a
(actually 2 different flavors of) "standard" regexp syntax/semantics, but
I don't know if typical regexp packages implement it or a superset.
If you're a software person of the compiler-writing flavor, NFSMs are
an essential part of the formal languages background you need to solidly
grok how a lexical-analyser generator (LEX, FLEX, ...) or parser generator
(YACC, Bison, ANTLR, ...) works.
--
-- Jonathan Thornburg <jth...@thp.univie.ac.at>
http://www.thp.univie.ac.at/~jthorn/home.html
Universitaet Wien (Vienna, Austria) / Institut fuer Theoretische Physik
Q: Only 7 countries have the death penalty for children. Which are they?
A: Congo, Iran, Nigeria, Pakistan[*], Saudi Arabia, United States, Yemen
[*] Pakistan moved to end this in July 2000. -- Amnesty International,
http://www.web.amnesty.org/ai.nsf/index/AMR511392000
Jan Vorbrueggen
> If you mean a FSM which randomly goes to different states based on certain
> probabilities, I really have no clue if it has been done, nor do any
> applications jump out at me.
This sounds like a Markov chain/model to me. Is there a relationship between
NFAs and Markov models?
If you're using speech recognition, you're using one variant of Markov models
called HMMs. I consider a type of hypothesis testing based on transition
probabilities (usually measured heuristically or estimated in some way).
Jan
Maynard Handley
amoli...@visi-dot-com.com wrote:
> In article <3A552F9E...@igs.net>, Paul DeMone <pde...@igs.net> wrote:
> >What exactly do you mean? An FSM with probablistic state transitions
> >governed by a pseudo random sequence generator like an LFSR or a linear
> >congruence modulo multiplier? Or governed by a truely random noise
> >source like amplified thermal background noise?
>
> _Compilers:_Principles,_Techniques,_and_Tools_
> discusses this. What you do with an NFA is that you essentially
> "take" all the transitions that are possible in a state,
> at once.
>
> Your current "state" is really the set of all the states
> of the NFA (Non-deterministic Finite Automaton) that you could
> be in. You take all the possible transitions out of all those
> states that you could be in. I think if one of the new
> states is a terminating state, you stop.
From a different point of view, all this comes across as very much like
"quantizing" traditional FSMs. Recall that to quantize a classical
"system", you construct the free complex vector space over the state space
of the classical system, ie the elements, |psi> of your quantized theory
are vectors associating a complex number with every possible state of of
the underlying classical system. You then define some linear scheme for
these states to evolve which is trivially defined by the underlying FSM.
The only real difference would appear to be that the NFA is filling that
vector with 1s and 0s rather than complex numbers. Obviously this works
well for simulation and hardware construction. For more general discussion
of mathematical properties, the more general free complex vector space
(with 0 treated as 0 and non-zero treated as 1 at the end of the day) may
be more powerful.
Maynard