dougs@hcx2.SSD.HARRIS.COM (08/20/88)
>Greg, lee@uhccux.uhcc.hawaii.edu claimed any NFSA can be simulated by >a DFSA (NFSA = Non-deterministic Finite State Automaton). Not so! >The simulation is 'try all paths with backtracking' However, in the >most general case, some of the false paths may not terminate. Therefore, >the NFSA, which magically avoids the wrong answers (that's why it's >non-deterministic) is more powerful. QED. >Henry Troup >Bell Northern Research does not make non-deterministic machines. >Therefore this is just me, shooting my mouth/foot off again. >/* End of text from hcx2:comp.misc */ /* Written 3:40 pm Aug 11, 1988 by hwt@leibniz.UUCP in hcx2:comp.misc */ Bell Northern Research couldn't make non-deterministic machines. They cannot be coded to operate on a computer. The main use for NFSA's is the ease of expressing regular expressions with them. But to recognize such expressions on a computer, a DFSA must be coded. Non-deterministic anythings can be simulated by a deterministic machine. Quoting Hopcroft and Ullman, "Introduction to Automata Theory, Languages, and Computation" : "Theorem 2.1 Let L be a set accepted by a nondeterministic finite automaton. Then there exists a deterministic finite automaton that accepts L." Since NFSA's and DFSA's accept the same set (language), they are equivalent. "Theorem 7.3 If L is accepted by a nondeterministic Turing machine, M1, then L is accepted by some deterministic Turing machine, M2." Same thing. Two machines are considered to be equivalent IF THEY ACCEPT THE SAME LANGUAGE, even if they may use different methods of getting there. A DFSA can always be constructed from an NFSA. There are several algorithms for doing this, and the time to completion may grow exponentially with the complexity of the NFSA, but an equivalent DFSA will always be found. Quoting Lewis and Papadimitriou, "Elements of the Theory of Computation" : "Theorem 2.3.1 For each nondeterministic finite automaton, there is an equivalent deterministic finite automaton." A four page proof follows in the book. There is a similar theorem for Turing machines. Doug Scofield dougs@hcx2.SSD.HARRIS.COM Harris Computer Systems Division 2101 W. Cypress Creek Rd. Ft. Lauderdale, FL 33069 (305) 973-5340
al@gtx.com (Alan Filipski) (08/27/88)
->Greg, lee@uhccux.uhcc.hawaii.edu claimed any NFSA can be simulated by
->a DFSA (NFSA = Non-deterministic Finite State Automaton). Not so!
->The simulation is 'try all paths with backtracking' However, in the
->most general case, some of the false paths may not terminate. Therefore,
->the NFSA, which magically avoids the wrong answers (that's why it's
->non-deterministic) is more powerful. QED.
QED nothing. of course you can write a stupid simulator that gets
caught in infinite loops. Try a breadth-first simulation instead of
depth-first. This is basically equivalent to the usual construction
that maps each subset of the NDFSA with a single state of the new
DFSA.
>Henry Troup
->Bell Northern Research does not make non-deterministic machines.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
( Alan Filipski, GTX Corp, 8836 N. 23rd Avenue, Phoenix, Arizona 85021, USA )
( {allegra,decvax,hplabs,amdahl,nsc}!sun!sunburn!gtx!al (602)870-1696 )
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~