CSci 301 Lecture Notes

Week Two, Thursday: Nonregular Languages

Consider the language B = {0ⁿ1ⁿ | n >= 0}.

A machine with a finite number of states cannot recognize this language because the number of zeroes is unlimited, so it can't use its states to remember how many zeroes there are and match them with ones.

Our intuition alone is insufficient for identifying nonregular languages. Consider

C = {w | w has an equal number of 0s and 1s}, and

D = {w | w has an equal number of occurrences of 01 and 10 as substrings}.

C is not regular, but D is! We need a formal method for testing languages for regularity.

The Pumping Lemma for Regular Languages

This theorem states that all regular languages have the property that the strings can be "pumped" if they are longer than some pumping length.

Formally, if A is a regular language, there is some number p where if s is a string in A of length at least p then x may be divided into three pieces, s = xyz, satisfying:

for each i >= 0, xyⁱz is an element of A,
|y| > 0, and
|xy| <= p.

The decimal expansion of 1/7 is 0.1428571428571...

Here the repeating part, "142857" corresponds to piece y, the "pumped" substring.

The decimal expansion of pi is 3.14159265359...

Notice that the decimal expansion of a rational number repeats, but the decimal expansion of an irrational number like pi does not. Because the rational number repeats, there is some finite machine that can recognize the language

E = {w | w is the decimal expansion of 1/7 to n digits where n >= 0}

Proof Idea: see page 78.

Example 1.38

Example 1.39

Example 1.40

Example 1.41

Example 1.42

Homework Assignment

Assigned Thursday, September 17, due Thursday, September 24, at beginning of class.

Chapter 1: Exercises 1.12, 1.16 (five points each).

Email: Richard dot J dot Wagner at gmail dot com