======================================================================== TextualDFAs Author: Bob Dondero ======================================================================== Note that: -- A DFA consists of states and transitions. -- Each transition is labeled with exactly one character or character set. -- In a DFA the next state is a function of the current state and the current character. The next state is a function of *only* the current state and the current character. -- A DFA indicates which state is the start state. -- A DFA indicates whether each state is an accepting state or a rejecting state. ------------------------------------------------------------------------ Textual representation of the "input contains an even number of zeros" DFA from the Wikipedia "Deterministic finite automaton" page. ------------------------------------------------------------------------ S1 (accept) <-- the start state 0: S2 1: S1 S2 (reject) 0: S1 1: S2 ------------------------------------------------------------------------ Textual representation of the "input contains an even number of zeros" DFA from the Wikipedia "Deterministic finite automaton" page with descriptive state names. Your Assignment 1 DFA should use descriptive state names. ------------------------------------------------------------------------ EVEN_NUMBER_OF_ZEROS (accept) <-- the start state 0: ODD_NUMBER_OF_ZEROS 1: EVEN_NUMBER_OF_ZEROS ODD_NUMBER_OF_ZEROS (reject) 0: EVEN_NUMBER_OF_ZEROS 1: ODD_NUMBER_OF_ZEROS ------------------------------------------------------------------------ Textual representation of the "Does the string have 'nano' in it" DFA from the Appendix of the "A Taste of C" lecture slides. ------------------------------------------------------------------------ START (reject) <-- the start state n: N other: START N (reject) n: N a: NA other: START NA (reject) n: NAN other: START NAN (reject) n: N a: NA o: NANO other: START NANO (accept) other: NANO