In the theory of computation, a deterministic finite state machine or deterministic finite automaton (DFA) is a finite state machine where for each pair of state and input symbol there is one and only one transition to a next state. DFAs recognize the set of regular languages and no other languages. Computation can be defined as finding a solution to a problem from given inputs by means of an algorithm. ... Fig. ... A regular language is a formal language (i. ...

A DFA will take in a string of input symbols. For each input symbol it will then transition to a state given by following a transition function. When the last input symbol has received it will either accept or reject the string depending on if it is in an accepting state or not.

Formal definition

A DFA is a 5-tuple, (S, Σ, T, s, A), consisting of In mathematics, a tuple is a finite sequence of objects (a list of a limited number of objects). ...

• a finite set of states (S)
• a finite set called the alphabet (Σ)
• a transition function (T : S × Σ → S)
• a start state (s ∈ S)
• a set of accept states (A ⊆ S)

Let M be a DFA such that M = (S, Σ, T, s, A), and X = x₀x₁ ... x_n be a string over the alphabet Σ. M accepts the string X if a sequence of states, r₀,r₁, ..., r_n, exists in S with the following conditions: In information processing, a state is the complete set of properties (for example, its energy level, etc. ... Partial plot of a function f. ... In the theory of computation, an accept state (sometimes referred to as an accepting state) is a state at which the machine has successfully performed its procedure. ...

1. r₀ = s
2. r_i+1 = T(r_i, x_i), for i = 0, ..., n-1
3. r_n ∈ A.

As shown in the first condition, the machine starts in the start state s. The second condition says that given each character of string X, the machine will transition from state to state as ruled by the transition function T. The last condition says that the machine accepts if the last input of X causes the machine to be in one of the accepting states. Otherwise, it is said to reject the string. The set of strings it accepts form a language, which is the language the DFA recognises.

Example

The following example is of a DFA M, with a binary alphabet, which determines if the input contains an even number of 0s.

M = (S, Σ, T, s, A) where

• Σ = {0, 1},
• S = {S₁, S₂},
• s = S₁,
• A = {S₁}, and
• T is defined by the following state transition table:

The state diagram for M is: In Automata Theory, a state transition table is a table describing the transition function T of a finite automaton. ... State diagrams are used to graphically represent finite state machines. ...

Simply put, the state S₁ represents that there has been an even number of 0s in the input so far, while S₂ signifies an odd number. A 1 in the input does not change the state of the automaton. When the input ends, the state will show whether the input contained an even number of 0s or not. This is an example of a DFA state diagram that I made using Visio. ...

The language of M can be described by the regular language given by this regular expression: A regular language is a formal language (i. ... A regular expression (abbreviated as regexp, regex, or regxp, with plural forms regexps, regexes, or regexen) is a string that describes or matches a set of strings, according to certain syntax rules. ...

Advantages and disadvantages

DFAs are one of the most practical models of computation, since there is a trivial linear time, constant-space, online algorithm to simulate a DFA on a stream of input. Given two DFAs there are efficient algorithms to find a DFA recognizing the union, intersection, and complements of the languages they recognize. There are also efficient algorithms to determine whether a DFA accepts any strings, whether a DFA accepts all strings, whether two DFAs recognize the same language, and to find the DFA with a minimum number of states for a particular regular language. A common approach in computer science to problem solving is offline computation. ...

On the other hand, DFAs are of strictly limited power in the languages they can recognize — many simple languages, including any problem that requires more than constant space to solve, cannot be recognized by a DFA. The classical example of a simply described language that no DFA can recognize is the language consisting of strings of the form aⁿbⁿ — some finite number of a's, followed by an equal number of b's. It can be shown that no DFA can have enough states to recognize such a language.

References

• Michael Sipser. Introduction to the Theory of Computation. PWS, Boston. 1997. ISBN 053494728X. Section 1.1: Finite Automata, pp.31–47. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp.152–155.

Michael Sipser is a Professor of Applied Mathematics in the Theory of Computation Group at MIT. His research area is complexity theory. ...

See also

• Acyclic deterministic finite automata
• Nondeterministic finite state machine
• Turing machine