Proof ATOC 1

Proof Project

The pumping lemma for regular languages:

If a language L is regular, there exists a constant p ≥ 1 such that every sentence s L of length ≥p can

be written as xyz =s satisfying these three conditions: |y| > 0, |xy| ≤ p, and for all i≥ 0, xyiz L.

L4 = {a k bn cn | k, n > 0 } {bi c j | i, j ≥ 0 } ∑= {a,b,c}

Note that L4 satisfy the pumping lemma but are not regular.

Write a report and the report (proofs) must be well written grammatically and technically. The quality and

style of your writing is expected to be suitable for publication.

 Problem:

a) Use the diagonalization argument to show that the set of functions from the set of natural numbers

to the set {true, false} is not countable. Show how self-refutation is used in the proof.

b) Use the pumping lemma to prove that a subset of L4 is not regular, and then use a closure property

of regular languages to prove that L4 is not regular.