(NFAs to DFAs), 9/18/17
Concepts, definitions, theorems:
- Every RE has an equivalent
NFA (p. 64) – recursive proof, last lecture
- Visualizing this recursive proof with a parse tree
- Recursive proofs vs. recusive
- Claim: every NFA has an equivalent DFA (Theorem 1.19,
- Proved by presenting an
algorithm for creating an DFA from an NFA (or converting an NFA to a DFA)
- A table-based algorithm
- First without epsilons,
then with epsilons
- Examples: strings
ending with 01, (1 U 01) *
- The set of DFA states is
of the set of NFA states.
- 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
- How to prove a language is regular?
- Create a DFA or an NFA
or a regular expression for it;
- (Finite languages are all regular)
- Use closure property of regular languages
property of RLs: The set of RLs is closed
under regular operations o, *, U
(also complement and intersection)
L = strings that do not contain substring “010”
o L1 = strings containing substring “010”
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
- section 1.2, from end of p. 54 ("EQUIVALENCE") to end of
- section 1.3, from middle of p. 66 ("EQUIVALENCE
- section 1.4 to end of page 79
- Know new definitions, understand new concepts
- Given an NFA (possibly with epsilon-transitions),
construct an equivalent DFA ("convert it" to a DFA).
- Understand concepts of equivalence, powerset, closure.
- Understand what makes a language finite or infinite.
- Understand why all finite
languages are regular.
- Be able to apply closure of RLs under regular
operations to show the language is regular
- Recursive proofs and algorithms apply whenever the
underlying set of structures can be defined recursively
- Example: trees, regular
- If a set if finite, of size n, the size of its powerset is 2^n.
possible to have an infinite language over a unary alphabet (i.e. single