David Coppit replied on 15 December 2004 14:21 > On Wed, 15 Dec 2004, Orton, Yves wrote: > > > The term "DFA::StateMachine" is like say "Car::Car". > > Right. > > > A DFA is by definition a state machine (it stands for > "determinisitic > > finite state automata"). And after a review of the code IMO > using the > > term DFA is a bad call. Normally "DFA" implies a specific type of > > implementation of a pattern matcher (as compared to say perls NFA > > [nondeterministic finite state automata] regex engine). > > I disagree. A DFA can be used to implement a pattern matcher, > but that's not all. A DFA is just a data structure.
But if you do a search for literature talking about DFA's _most_ will be related to pattern matching. For instance I just googled for "determinisitc finite state automata" and most of this hits that i followed concerned pattern matching or used the language of pattern matching to explain DFA's. Im not arguing that you are wrong about this, just that the primary association in most folks heads when they see DFA will be pattern matching. In fact when discussing DFA's most of the literature discusses the "alphabet" the DFA will operate on, and the "language" it is designed to accept. (http://en.wikipedia.org/wiki/Deterministic_finite_automaton) > > > This is more of a turing machine than what is normally called a DFA. A > > term that you encounter in the literature for this type of construct is > > an FSA (finite state automaton/aka turing machine) which doesn't have > > such a strong association to pattern matching. > > FSA is a more general term that encompasses both DFA and NFA. Not having > checked the code, I'm not sure if it supports nondeterministic transitions. I didnt see any support for non deterministic transitions. And yes FSA does include DFA and NFA's but it also includes DTM's and NDTM's (determinisitic turing machines and non determinisitic turing machines). My point was that FSA's emphasize the point that there is external memory and that there are "actions" involved wheras DFA/NFA's normally have no "actions". > > However, you're incorrect in saying FSA==turing machine. The key > limitation is that FSAs are *finite* and a turing machine is not. More > details: > > http://en.wikipedia.org/wiki/Finite_state_machine > http://www.cs.wm.edu/~coppit/wiki/index.php?title=Quals:_Computer_Theory_and _Algorithms > >I'm not sure if this discussion helps the OP any, but I thought I should clarify. :) Actually i think you are wrong here. And the links you provide seem to back me up. A turing machine does NOT have an infinte number of states. It has an infinite memory. From the wikipedia article we see the following: (note point #3) <quote> More precisely, a Turing machine consists of: 1. A tape which is divided into cells, one next to the other. Each cell contains a symbol from some finite alphabet. The alphabet contains a special blank symbol (here written as '0') and one or more other symbols. The tape is assumed to be arbitrarily extendible to the left and to the right, i.e., the Turing machine is always supplied with as much tape as it needs for its computation. Cells that have not been written to before are assumed to be filled with the blank symbol. 2. A head that can read and write symbols on the tape and move left and right. 3. A state register that stores the state of the Turing machine. The number of different states is always finite and there is one special start state with which the state register is initialized. 4. An action table (or transition function) that tells the machine what symbol to write, how to move the head ('L' for one step left, and 'R' for one step right) and what its new state will be, given the symbol it has just read on the tape and the state it is currently in. If there is no entry in the table for the current combination of symbol and state then the machine will halt. </quote> As far as I know a DFA is defined as a finite automaton where each state/input combination can result in only one legal transition. (http://en.wikipedia.org/wiki/Finite_state_machine) An NFA of course can have multiple transitions for a given state/input combination. (You can see this definition in regards to determinisitc turing machines and non deterministic turing machines in the wikipedia article as well.) >P.S. My whiz-bang super-fast computer is also equivalent in power to a DFA because its memory is finite. Well, yeah sure, because the memory is finite and it only allows for a single transition from a given state and input it is formally a DFA. However this formal equivelency is a bit useless. DFA's have no memory so they cant handle type 0 languages. However as we all know your desktop does handle type 0 languages as in practice most statements written in type 0 languages dont need infinte memory to resolve. But a DFA cant recurse, there is NO stack just states. So to put it as the article you linked to did: "For example, a Turing machine describing an algorithm may have a few hundred states, while the equivalent DFA on a given machine has quadrillions." So the only way you can map a modern computer on to a DFA is to say that every given CPU state and memory configuration represents a state. Which isnt so useful a model. We program computers assuming that they are Turing Machines not DFA's (at least not the traditional state transition table form of DFA). I think part of the problem here is that the term "state" is not always well defined. For instance in the turing machine article on wikipedia they use two different meanings of state. The first is one where the state of the machine is distinct from what is stored in its memory. However in the section following discussing "Comparison with real machines" where it says your desktop is essentially a DFA they use "state" to refer to the combination of both CPU state and memory configuration. This IMO just confuses everything. If we define state to be regardless of memory configuration then a von-neuman machine like your desktop is much closer to a turing machine than to the traditional DFA. If we define state to be the combination of memory configuration and CPU state then we can just call a turing machine a DIA (deterministic infinite state automata). I have no idea if this discussion belongs on the module list, if you are interested in discussing it further id be happy to do so offlist. :-) Cheers. yves
