A finite state machine in which every state has exactly one transition for each possible input symbol, so its behavior on any input string is completely determined; used to recognize regular languages such as those matched by regular expressions.
Facts
Core PrincipleUpon reading each symbol, the automaton jumps deterministically from one state to another by following the single transition for that symbol. 1 Connections
In Field
Invented By
Dana Scott co-authored the 1959 paper with Michael Rabin that formalized deterministic and nondeterministic finite automata and proved their equivalence.
Michael O. Rabin co-authored the 1959 paper with Dana Scott that formalized deterministic and nondeterministic finite automata and proved their equivalence.
Sources
1. Deterministic finite automaton - Wikipedia
Formal definition
Upon reading a symbol, a DFA jumps deterministically from one state to another by following the transition arrow.
In Group: Models of Computation and Automata, Lead
In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA), also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automaton (DFSA), is a finite-state machine that accepts or rejects a given string of symbols, by running through a state sequence uniquely determined by the string.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.