Lecture 4 (DFAs and NFAs), 2/01/06

Concepts, definitions (in italics):

• Equivalent FSAs
• Minimal FSAs
• Deterministic Finite State Automata (DFAs)
• Nondeterministic Finite State Automata (NFAs)

Reading and Homework:

• Finish all reading for lectures 1-3
• Section 1.2, up to end of p. 54 ("EQUIVALENCE")
• Homework 2 (due next Wednesday)

Skills:

• Know new definitions, understand new concepts
• Construct a DFA for a given language (described in English or as a regular expression)
• Using the definition of computation, prove simple statements about languages of DFAs
  (such as what happens if q₀ is in F, or if F is empty, or if F = Q)
• Given an FSA, determine whether or not it is deterministic
• Understand why DFAs are special cases of NFAs, but not vice versa
• Given an NFA M and an input string w, does M accept w?
• Given an NFA, describe its language
• Construct an NFA for a given language

Notes:

• For a given language, there may be multiple FSAs that recognize it; FSAs with fewer states are preferable.
• Examples of nondeterminism: w ends in (or contains) a substring w'
• Unlike DFAs, NFAs are non-constructive (it is not straightforward to simulate them)
• Note: just as for DFAs, the book's definition of NFAs views d as a mapping; we continue to view d as a set of triples. 
• We are skipping the conversion from a DFA to a minimal DFA (it's not in our textbook, but some other textbooks have it).