Lecture 8 (Proving Languages Non-regular), 11/15/06

Concepts, definitions (in italics):

• The contrapositive and the converse of a statement
• Regular Language Property (true of all regular languages):

  If L is regular, then:
  there exists some number p such that for all w in L of length ≥ p,
  w = xyz, where |y| ≥ 1,  |xy| ≤ p and xyⁱz is in L for all i ≥ 0.

• Pumping Lemma: if a language does not have the regular language property, it is not regular
• Another method of showing a language is not regular: applying the contrapositive of RL closure rules.
• Contrapositive: if L1 op L2 gives a non-regular language (where op is one of the operations under which regular languages are closed), then at least one of L1, L2 must be non-regular.

Reading:

• section 1.4 (make sure to study the examples)

Skills:

• Know new definitions, understand new concepts.
• Be able to prove the Regular Language Property
• Be able to apply the Pumping lemma to show that a given language is not regular.
• Be able to apply RL closure rules to show that a language is not regular.

Notes:

• If a language if infinite, then for any p ≥ 0, it contains strings of length ≥ p
• For a statement of the form "if A then B", the converse is "if not A, then not B"; the contrapositive is "if not B, then not A".  The contrapositive is equivalent to the original, but the converse is not. 
• Ways to prove that a language is not regular
  • Use the Pumping Lemma to show that it does not have the RL property
  • Use the closure rules for RLs
• Example of a non-regular language: {0ⁿ 1ⁿ : n ≥ 0} (proven with the Pumping Lemma)
• {0*1*: # of 0's same as # of 1's} is not regular:
      {0ⁿ 1ⁿ : n ≥ 0} is the intersection of { {0, 1}*: # of 0's same as # of 1's} and {0*1*}