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

         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:

 

Skills: