Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection, and complement

Answer: Explained

Explanation:

To prove that L is not a regular language, we will use a proof by contradiction. Assume

that L is regular. Then by the Pumping Lemma for Regular Languages, there exists a

pumping length, p for L such that for any string s ∈ L where |s| ≥ p, s = xyz subject

to the following conditions:

(a) |y| > 0

(b) |xy| ≤ p, and

(c) ∀i > 0, xyi

z ∈ L.

Choose s = 0p10p

. Clearly, |s| ≥ p and s ∈ L. By condition (b) above, it follows that

x and y are composed only of zeros. By condition (a), it follows that y = 0k

for some

k > 0. Per (c), we can take i = 0 and the resulting string will still be in L. Thus,

xy0

z should be in L. xy0

z = xz = 0 (p-k) 10p

. But, this is clearly not in L. This is a

contradiction with the pumping lemma. Therefore our assumption that L is regular is

incorrect, and L is not a regular language.

b. L = {wtw | w, t ∈ {0, 1}

+}.