Lecture 6 (NFA to DFAs), 2/08/06

Concepts, definitions (in italics):

• Constructing an NFA from an RE.
• A computation tree for an NFA M and input string w -- shows all possible computations on M on w (vs. a computation path for a DFA).
• Computation trees for NFAs with e-transitions
• The powerset of a set.
• Creating an automaton whose set of states is the powerset of the set of states of another automaton.
• Every NFA has an equivalent DFA (Theorem 1.19)
• Unreachable FSA states.
• If an FSA contains an unreachable state q, then it is equivalent to the FSA with q and all adjacent transitions removed.
• The algorithm for converting a given an NFA to an equivalent DFA.

Reading:

• section 1.2, from end of p. 54 ("EQUIVALENCE") to end
• Do homework 3 for next Wednesday.

Skills:

• Know new definitions, understand new concepts
• Given an RE, construct an equivalent NFA.
• Given an NFA, construct an equivalent DFA.
• Prove that if an FSA contains an unreachable state q, then it is equivalent to the FSA with q and all adjacent transitions removed.
• Given an NFA M and an input string w, construct the computation tree

Notes:

• If a set if finite, of size k, the size of its powerset is 2^k.
• The cardinality of a power set of a countable (infinite) set is uncountable.
• The end of section 1.3, which we are skipping, is the remaining algorithm, converting from a DFA to a regular expression