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

Concepts, definitions, theorems:

         How to use tables to represent NFAs

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

         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 = 02k 13m 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:

Skills:

Note:

         all finite languages are regular