CMPSC 138 Chapter Notes - Chapter 2: Nondeterministic Algorithm, Backtracking, Dfa Records
Document Summary
Finite accepters are automata that are deterministic in their operations: Process an input string, consisting of a sequence of symbols. Make transitions from one state to another, depending on the current state and the current input symbol. Deterministic finite acceptor = dfa = the quintuple = (, , , ), ) = finite set of symbols called the input alphabet. : = a total function called the transition function. Transition graph = a representation of finite automata, using vertices to represent states and edges to represent transition; labels on vertices are the names of the states, labels on the edges are the current values of the input symbol. If = (, , , ), ) is a dfa with transition graph 0, 0 has exactly || vertices. : is an extended transition function. Is a string rather than a single symbol, whose value gives the state the automaton will be in after reading the string.
