**Lecture 5
(REs to NFAs), 9/13/17**

**Concepts, definitions, theorems:**

·
Review:
(1^{3})* vs (1*)^{3} – understand the difference

·
Alternately,
(a U b)* vs (ab) * – understand the difference

- NFA
*transitions*– triples in Q x*Sigma*x Q_{epsilon}

·
DFAs
are special cases of NFAs, but not vice versa

·
This
implies that the set of DFA languages is a subset of the set of NFA languages

·
Creating
an NFA for simple regular expressions: epsilon, null, c

·
Creating
an NFA whose language is the union/concatenation/star of languages for two/one
other NFAs.

·
Equal expressiveness of REs, DFAs, NFAs (*Regular
Language Theorem*):

for any fixed alphabet Sigma, the
sets of languages described by REs, recognized by DFAs, accepted by NFAs are
the same

·
This
will be proved as 3 separate claims:

1.
For every RE, there is an equivalent NFA (proved today)

o Implies that RE languages are a
subset of NFA languages

2. For
every NFA, there is an equivalent DFA (proved next time)

o Implies that NFA languages are a
subset of DFA languages

3. For
every DFA, there is an equivalent RE (we’ll skip proof, but it’s Lemma 1.60 in
book)

o Implies that DFA languages are a
subset of RE languages

·
To
prove k sets to be equivalent, we can show that each is a subset of the next
(in a k-cycle); this is because of the transitivity of the subset relation

·
For
a set that is defined recursively
(such as Binary Trees or Regular Expressions) a claim about all of its members
must be proved recursively

o *Base cases* are
proved directly

o Other
cases must use *recursive* (*inductive) assumption*

·
So
Claim 1 is proved with a *recursive proof *

o Follows the
same flow as recursive definitions and recursive algorithms

o Recursive
assumption in proofs is like recursive call in an algorithm

**Reading:**

- Section 1.2, from end of p.
58 ("CLOSURE") to the end
- Section 1.3, from middle of p. 66 ("EQUIVALENCE
") to
figure 1.59
- Understand the concept of recursive definitions and
proofs (review if necessary – check out “recursive definition” in
Wikipedia)

**Skills:**

- 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
- Be able to convert regular expressions to NFAs