ABSTRACT
Deterministic finite automata (DFA) design is really low level programming; hence, subtle mistakes are quite likely. It is important to avoid them through best practices, clearly understanding the language for which a DFA is to be developed, and double-checking the DFA designs. One must check that the DFA accepts all strings. This chapter illustrates these ideas in action and presents a markdown language that makes us treat DFA design like assembly language programming through the use of clear state-names and comments to describe states and transitions. Languages must be ideally specified using any combination of these approaches: a precise English description; a clear set builder (comprehension) description; through a sufficient number of positive examples and negative examples; and descriptions that take different perspectives. Minimal DFA are unique for a given regular language—this is the Myhill-Nerode theorem.
