**Lecture
6 (NFAs to DFAs), 2/1/18**

**Concepts, definitions, theorems:**

·
How to use tables to represent NFAs

- Cannot use same format as for DFAs

o Can
use one where table entries are sets (that*'*s what the book does)

·
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)

o A table-based algorithm

o DFA states are members of the *powerset* of the set of NFA
states.

o First without epsilons, then with epsilons

o Examples: strings ending with 01, (1 **U** 01) *

·
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

·
There
are languages that are *not regular*

·
Examples
of languages that are not regular:

o 0^n1^n over alphabet {0,1} is not
regular

o *ww* over alphabet {a,b, . . ., z} is
not regular

·
How to prove a language is regular?

o Create a DFA or an NFA or a regular
expression for it;

o Use *closure* *property of regular
languages*

·
Concept
of *closure *(of a set under an
operation)

o Examples: naturals, integers, reals,
complex numbers

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

·
Why regular languages are closed
under union, complement, star, complement, intersection

·
How
to use closure property to prove language regular

o Show how these proofs would look

·
Example 1: L = strings over {a,b} that do not contain substring "aa"

o L1
= strings containing substring "aa"

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

·
Example 2: L2 = 0^{2k} 1^{3m}
where k, m >= 0

o
L2 equals the intersection of 0*1*
and the language {# 0's is
divisible by 2, # of 1's
divisible by 3}, so it must be regular

**Reading:**

- section 1.2, from end of p. 54 ("EQUIVALENCE")
to end of section
- Theorems 1.45, 1.47, 1.49 (which can be proved with
either REs or NFAs)

**Skills:**

- Know new definitions, understand new concepts
- Given an NFA (possibly with epsilon-transitions),
construct an equivalent DFA ("convert it" to a DFA).
- Understand concept of
*closure*. - Be able to apply closure of RLs under regular
operations to show the language is regular

**Note: **

·
all finite languages are regular