Deterministic Finite-State Machine
Jump to navigation
Jump to search
A Deterministic Finite-State Machine is a Finite-State Machine that ...
References
2011
- http://en.wikipedia.org/wiki/Deterministic_finite_automaton
- In the theory of computation and automata theory, a deterministic finite state machine — also known as deterministic finite automaton (DFA) — is a finite state machine accepting finite strings of symbols. For each state, there is a transition arrow leading out to a next state for each symbol. Upon reading a symbol, a DFA jumps deterministically from a state to another by following the transition arrow. Deterministic means that there is only one outcome (i.e. move to next state when the symbol matches (S0 -> S1) or move back to the same state (S0 -> S0)). A DFA has a start state (denoted graphically by an arrow coming in from nowhere) where computations begin, and a set of accept states (denoted graphically by a double circle) which help define when a computation is successful.
DFAs recognize exactly the set of regular languages which are, among other things, useful for doing lexical analysis and pattern matching.
- In the theory of computation and automata theory, a deterministic finite state machine — also known as deterministic finite automaton (DFA) — is a finite state machine accepting finite strings of symbols. For each state, there is a transition arrow leading out to a next state for each symbol. Upon reading a symbol, a DFA jumps deterministically from a state to another by following the transition arrow. Deterministic means that there is only one outcome (i.e. move to next state when the symbol matches (S0 -> S1) or move back to the same state (S0 -> S0)). A DFA has a start state (denoted graphically by an arrow coming in from nowhere) where computations begin, and a set of accept states (denoted graphically by a double circle) which help define when a computation is successful.