**Lecture 5
(REs to NFAs), 1/30/18**

**Concepts, definitions, theorems:**

·
Another
NFA example: S = {a,b}, L = {strings with substring "aa"}

·
When checking if an FSA is correct, need
to check both directions:

·
All strings in L are accepted

·
All strings not in L are rejected

- Computation is a sequence of transitions, or a path in
the FSA starting with initial state
*Epsilon-transitions*- FSA
*transitions*-- triples in Q x**S**x Q - NFA
*transitions*-- triples in Q x**S**x Q_{e} - Computations with
**e***-transitions*still spell out the input string along their transitions

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

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

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

·
This
will be proved as 3 separate claims:

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

·
Implies
that RE languages are a subset of NFA languages

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

·
Implies
that NFA languages are a subset of DFA languages

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

·
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

·
Claim
1 applies to any regular expression. For a set that is defined recursively (such as the set of Regular
Expressions) a claim about all of its members must be proved *recursively. *

·
This proof follows the same flow as the recursive
definition.

·
*Base
cases* are proved directly

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

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

**Reading:**

- Section 1.2, from end of p.
58 ("CLOSURE") to the end
- Section 1.3, from middle of p. 66 ("EQUIVALENCE") through 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
- Using the definition of computation, prove simple
statements about languages of FSAs

(what happens if q_{0}is in F, or if F is empty, or if F = Q) - Construct an DFA or an NFA for a given language
- 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