Deterministic finite-state machine

From Wikipedia, the free encyclopedia

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.

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 been received it will either accept or reject the string depending on whether the DFA is in an accepting state or a non-accepting state.

Contents 1 Formal definition 2 Example 3 Advantages and disadvantages 4 See also 5 References

[edit] Formal definition

A DFA is a 5-tuple, (S, Σ, T, s, A), consisting of

• 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:

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 according to the transition function T. The last condition says that the machine accepts X if the last input of X causes the machine to halt in one of the accepting states. Otherwise, it is said to reject the string. The set of strings the DFA accepts form a language, which is the language the DFA recognizes.

A DFA without a list of accept states and without a designated starting state is known as a transition system or semiautomaton.

[edit] Example

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

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

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

	0	1
S1	S2	S1
S2	S1	S2

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. If the language did contain an even number of 0s, M will finish in state S₁, an accepting state, so the input string will be accepted.

The language of M is the regular language given by the regular expression (1^*(0(1)^*0)^*)^*

[edit] 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 of the two DFAs
• the intersection of the two DFAs
• complements of the languages the DFAs 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
• the DFA with a minimum number of states for a particular regular language

DFAs are equivalent in computing power to nondeterministic finite automata.

On the other hand, Finite State Automata 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 bracket language, that is, language that consists of properly paired brackets, such as (()()). More formally the language consisting of strings of the form aⁿbⁿ — some finite number of a's, followed by an equal number of b's. If there is no limit to recursion (i.e., you can always embed another pair of brackets inside) it would require an infinite amount of states to recognize.

[edit] See also

• Acyclic deterministic finite automata
• Nondeterministic finite state machine
• Turing machine
• Read only right moving Turing Machines
• Monadic second-order logic

[edit] References

• Michael Sipser, Introduction to the Theory of Computation. PWS, Boston. 1997. ISBN 0-534-94728-X. Section 1.1: Finite Automata, pp.31–47. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp.152–155.4.4 DFA can accept only regular language

Automata theory: formal languages and formal grammars

Chomsky hierarchy	Grammars	Languages	Minimal automaton
Type-0	Unrestricted	Recursively enumerable	Turing machine
n/a	(no common name)	Recursive	Decider
Type-1	Context-sensitive	Context-sensitive	Linear-bounded
n/a	Indexed	Indexed	Nested stack
n/a	Tree-adjoining etc.	(Mildly context-sensitive)	Embedded pushdown
Type-2	Context-free	Context-free	Nondeterministic pushdown
n/a	Deterministic context-free	Deterministic context-free	Deterministic pushdown
Type-3	Regular	Regular	Finite
n/a		Star-free	Counter-Free
Each category of languages or grammars is a proper subset of the category directly above it, and any automaton in each category has an equivalent automaton in the category directly above it.