Finite automaton

A discrete manner of defining a computational entity, usually a regular expression. The formal definition is in the form of a 5-tuple A=(Q,Sigma,delta,q₀,F), where Q is the set of states in A, Sigma is the alphabet of A, delta is the transition function: q X a -> q₁, where q, q₁ are an element of Q and a is an element of Sigma, q₀ is the start state and F is the set of accept states. A will accept a string on a regular language, if the string terminates on one of the accept states of A. See: PERL and regular expression

This device, more accurately known as a finite state automaton, accepts strings by starting in the start state, then hopping from state to state reading a character as indicated by the transition function. Iff it finishes reading the given string in a state in F, the string is accepted.

These automata also come in a nondeterministic variant, in which the transition relation is not necessarily a function.

There are several different types of finite automata, which are generally useful as formalisms. The above writeup by sahib! describes only deterministic finite automata (DFA). There are also:

• nondeterministic finite automata (NFA), where, as mentioned by rp, the transition relation may not necessarily be a function.
• NFA with epsilon transitions, which are the same as NFA, except that they can make transitions even when an input symbol is not read.
• Two-way DFA (2DFA), which are capable of moving both back and forward on the tape of input symbols. They are similar to Turing machines except that they do not have the ability to modify symbols on the input tape.

It can be shown that all of these constructions are equivalent, in that they all accept the same formal language: the regular languages. It can be shown that a DFA can be built out of an NFA (although the number of states in the resulting DFA in general has the cardinality of the power set of the states in the original NFA). NFA with epsilon transitions can be converted into NFA without epsilon transitions, by creating an NFA based on states that are reachable via epsilon transitions. 2DFA can be converted into NFA by considering the crossing sequences of the 2DFA (the states entered by the 2DFA as it reads any input symbol on the tape). Other permutations such as a two-way nondeterministic finite automaton can also similarly equivalent. This is why it is usual to speak simply of finite automata without qualification, any of them can be converted into any of the others.