| Deterministic Finite Automaton |
Article Index for Deterministic |
Website Links For Machine |
Information AboutDeterministic Finite Automaton |
| CATEGORIES ABOUT DETERMINISTIC FINITE-STATE MACHINE | |
| computational models | |
| automata | |
|
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. FORMAL DEFINITION A DFA is a 5- Tuple , (''S'', Σ, ''T'', ''s'', ''A''), consisting of
Let M be a DFA such that M = (''S'', Σ, ''T'', ''s'', ''B''), and ''X = x0x1 ... xn'' be a string over the alphabet Σ. M accepts the string ''X'' if a sequence of states, ''r0,r1, ..., rn'', exists in ''S'' with the following conditions: # ''r0'' = ''s'' # ''ri+1'' = ''T''(''ri'', ''xi''), for ''i'' = ''0, ..., n-1'' # ''rn'' ∈ ''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. A DFA without a list of accept states and without a designated starting state is known as a Transition System or Semiautomaton . EXAMPLE The following example is of a DFA ''M'', with a binary alphabet, which requires that the input contains an even number of 0s. for ''M'']] ''M'' = (''S'', Σ, ''T'', ''s'', ''A'') where
Simply put, the state ''S''1 represents that there has been an even number of 0s in the input so far, while ''S''2 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. The language of ''M'' is the Regular Language given by the Regular Expression
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. DFAs are equivalent in computing power to Nondeterministic Finite Automata . 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 bracket language, that is language that consists of properly paired brackets, such as (()()). More formally the language consisting of strings of the form anbn — 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. SEE ALSO
REFERENCES
|
|
|