**Lecture 6
(NFAs to DFAs), 9/18/17**

**Concepts, definitions, theorems:**

- Every RE has an
*equivalent*NFA (p. 64) – recursive proof, last lecture - Visualizing this recursive proof with a parse tree
- Recursive proofs vs. recusive
algorithms
- Claim: every NFA has an equivalent DFA (Theorem 1.19,
proof p.55)
- Proved by presenting an
algorithm for creating an DFA from an NFA (or
*converting*an NFA to a DFA) - A table-based algorithm
- First without epsilons,
then with epsilons
- Examples: strings
ending with 01, (1
**U**01) * - The set of DFA states is
the
*powerset*of the set of NFA states. - Also, every DFA has an equivalent RE (we won’t do this,
but it’s in the textbook)
- Equal expressiveness of REs, DFAs, NFAs (
*Regular Language Theorem*): for any fixed alphabet S, the sets of languages described by REs, recognized by DFAs, accepted by NFAs are the same - How to prove a language is regular?

- Create a DFA or an NFA
or a regular expression for it;
- (Finite languages are all regular)
- Use
*closure**property of regular languages*

·
Closure
property of RLs: The set of RLs is *closed*
under regular operations o, *, U
(also complement and intersection)

·
Example:
L = strings that do not contain substring “010”

o L1 = strings containing substring “010”

o L is a *complement* of L1

o We know that L1 is regular (can
easily create NFA for it), so L must be regular too

**Reading:**

- section 1.2, from end of p. 54 ("EQUIVALENCE") to end of
section
- section 1.3, from middle of p. 66 ("EQUIVALENCE
") to
figure 1.59
- section 1.4 to end of page 79

**Skills:**

- Know new definitions, understand new concepts
- Given an NFA (possibly with epsilon-transitions),
construct an equivalent DFA ("convert it" to a DFA).
- Understand concepts of
*equivalence*,*powerset*,*closure*. - Understand what makes a language
*finite*or*infinite*. - Understand why all
*finite*languages are regular. - Be able to apply closure of RLs under regular
operations to show the language is regular

**Notes:**

- Recursive proofs and algorithms apply whenever the
underlying set of structures can be defined recursively
- Example: trees, regular
expressions
- If a set if finite, of size n, the size of its powerset is 2^n.
- It’s
possible to have an infinite language over a unary alphabet (i.e. single
character);
ex:
**1***