Lecture 7 (Closure Rules), 02/13/06

Concepts, definitions (in italics):

• Equal expressiveness of REs, DFAs, NFAs (Regular Language Theorem): for a fixed alphabet S, the sets of languages described by REs, recognized by DFAs, recognized by NFAs are the same
• To prove that a language is regular: create a DFA or an NFA or a regular expression for it.
• Closure rules for regular languages: regular languages are closed under regular operations, as well as complement, intersection, and set difference.
• Another method of showing a language is regular: applying RL closure rules (if L1 and L2 are regular, then so is L1 op L2).
• For every regular language, there is a regular expression, which itself is a string, so the set of regular languages is no larger than the set of strings.
• The set of regular languages is countable, while the set of all languages is uncountable.
• By the counting argument, there exist languages that are not regular.

Reading:

• finish all reading from before

Skills:

• Know new definitions, understand new concepts.
• Be able to prove that regular languages are closed under complement, intersection, set difference.
• Be able to apply RL closure rules to show that a language is regular (see example below).

Notes:

• How to prove that a language is regular
  • Create a DFA or an NFA or a regular expression for it;
  • Use the closure properties of RLs
• Example: the set of strings whose length is divisible by 5 but not by 6 is regular.
• Intersection(L1, L2) = compl( union(compl(L1), compl(L2)) )
• Diff(L1, L2) = intersection(L1, compl(L2))
• The cardinality of an infinite set of strings over any finite alphabet is countable.