1. Pumping Lemma:
a. Is the following language a regular language? (Use pumping
lemma in proof.) L = {0n 1n 2n | n ≥ 0}
b. What is (i.e., define) the CFL pumping lemma?
Use the pumping lemma to show that the following languages are
not regular
(c) (5 pts) Let Σ = {0, 1, −, =} and
SUB = {x = y − z | x, y, z are binary integers, and x is the
result of the subtraction of z from y}. For example: 1 = 1 − 0, 10
= 11 − 01 are strings in SUB but not 1 = 1 − 1 or 11 = 11 − 10.
Use the Pumping Lemma to show that the following languages are
not regular.
(a) {ai bj | i > j}
(b) {apaq | for all integers p and q where
q is a prime number and p is not prime}.
Let a < c < b, and let f be defined on [a,b]. Show that f
∈ R[a,b] if and only if f ∈ R[a, c] and f ∈ R[c, b]. Moreover,
Integral a,b f = integral a,c f + integral c,b f .
Use the pumping lemma to show that the following languages are
not regular.
A a. A1={0^n 1^n 2^n | n≥0}
b. A2 = {www | w ∈ {a,b}∗}
A c. A3 ={a^2^n | n≥0} (Here, a^2^n means a string of 2^n
a’s.)
A ={a3n |n > 0 }