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

Concepts, definitions, theorems:

·         Review: (13)* vs (1*)3 – understand the difference

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

·         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