Wikipedia has a pretty good article, too.
Discrete Finite Automata: DFAs
An FSA (sometimes "finite-state machine," FSM) is an imaginary sort of machine which is a set of states and a set of transitions to other states. The article notes that collision detection is an FSA problem, but I've been raised on thinking of FSAs as being language parsing machines. A very simple FSA is a discrete finite automata (or DFA). A DFA has a finite number of states, and given an event - like finding a 0 or a 1 an "A" or a "B", the machine moves to another state.
An example is a machine which operates on the alphabet {A, B} and runs as long as it sees alternating "A"s and "B"s, e.g. ABABAB, but not ABBA. I.E., the machine runs on the alphabet {A, B} and accepts the language of zero or more instances of the string "AB."
We'll always start in a state called S0. In S0, there is a possible transition on A to S1 and on B a transition to S2. In S1, there is a transition on B to S2, in S2, we transition to S1. On all other events, transition to Serror, indicating that the machine is in a "reject" state. So a graph of this might look like this:
S0: A -> S1
B -> S2
S1: B -> S2
A -> Serror
S2: A -> S1
B -> Serror
Serror: A or B -> Serror.
So now if we start in S0 and feed the machine the inputs A, B, A it goes through states:
S0, S1, S2, S1.
If we feed the machine ABBA, it goes through states:
S0, S1, S2, Serror, Serror, and we know ABBA is not in our "language" of alternating As and Bs.
(I am simplifying a little here - technically all DFAs have an "accept" state as well as an error state, and there's an implicit "end of word" character. If you care, imagine that on "end of word", S1 and S2 transition to SAccept.)
It is also worth noting here that we can modify DFAs - for example, we can have DFAs with stack behavior (when taking input, they look at the top of an imaginary stack, and then push or pop something on/from the stack). DFAs with stacks are generally called "Push-down automata." PDAs can actually parse languages like C++, or Python, or Algol, or Lisp. They're very powerful indeed.
So in short, a DFA is a very powerful tool, and one that is generally well-researched, and if you believe that any math problem is actually a language problem (hint: it is), then a DFA can actually be created that solves pretty much any problem. And of course, because they are well-researched and easy to model on a computer, they get used quite a lot.
Non-Deterministic Finite-State Automata
There are also a whole family of FSA called non-deterministic finite state automata, or NDFA. These machines are generally somewhat difficult to conceptualize, because at any given time we need to imagine the machine as being in a set of one or more states. We might have a rule like this:
S0: A -> S1
A -> S2
B -> S3
i.e.: When in state S0, if given the input A, we now transition to states S1 and S2.
It is often said that when using an NDFA, these kinds of transitions invite us to think of the machine as splitting into several different machines, and if any of those machines reach an accept state, then the word is in our language.
2 comments:
It's worth pointing out here that for simple FSMs (those with no stack or tape), nondeterminism doesn't actually change the set of languages the machine can define.
It should be obvious that anything definable as a deterministic machine is definable using nondeterminism (just don't exercise the option of nondeterminism).
Recognizing the NDFA's can be converted into DFA's is a little trickier. The key is recognizing that you have to change what a "state" represents. If you original NDFA has some states (S0, S1, and S2 for example) then you can make a DFA where each state represents a subset of the possible states of your NDFA (so you'd have [S0], [S1], [S2], [S0,S1], [S0, S2], [S1, S2], [S0, S1, S2]) (for mathy folks you may recognize this as the "power set" of the set of states of the NDFA). Thus as the DFA receives input, its current state represents the set of all states the NDFA may be in given the same sequence of input.
This is of course a terribly inefficient way to go about making a DFA since it has 2^(number of states in the NDFA) states. A lot of work has been done in trying to reduce the number of states in a DFA, but to my knowledge the question of "how do we take an arbitrary DFA and turn it into an NDFA with a given level of parallelism" hasn't really been tackled (of course I could be wrong, there's a lot of literature). I look forward to seeing what you turn up in this area.
Actually, I'm getting to some of this on my next article - though I'm glad to hear that people have been trying to find reduction methods for DFAs and that I'm not the only one who thinks it is possible but very difficult.
Post a Comment