A deterministic finite automaton is a finite-state machine that accepts or rejects a given string of symbols by running through a state sequence determined by the string. It was first introduced in 1943 by Warren McCulloch and Walter Pitts, and is used to solve various specific problems such as lexical analysis and pattern matching. DFAs have been generalized to nondeterministic finite automata which recognize the set of regular languages.
Carnegie Mellon University
Spring 2015
A foundational course that introduces formal languages, automata, computability, and complexity theories, including finite automata, Turing machines, and P/NP classes.
No concepts data
+ 35 more concepts