Concepts, definitions, theorems:

• Table-based and set-based representations of NFAs
• NFAs with e-transitions
• Creating an NFA whose language is the union/concatenation/star of languages for two other NFAs.
• Every RE has an equivalent NFA (p. 64)
• Proof by structural induction -- for a set that is defined recursively

• Section 1.3, from middle of p. 66 ("EQUIVALENCE ") to end of p. 69 (figure 1.59)

• Know new definitions, understand new concepts
• Understand the proof that for any RE, there exists an NFA accepting the same language
• Understand why the construction for STAR needed a new initial state

• NFA ex: k'th letter from end of w is c
• NFA ex: the number of characters is divisible by 2 or by 3
• In the next class, we'll do an example of converting an RE to an NFA.