Question

This question allows you to practice proving a language is non-regular via the Pumping Lemma. Using the Pumping Lemma (Theorem 1.70), give formal proofs that the following languages are not regular: (a) L = {www | W € {0,1}* }. (b) L = {1"01" m, n >0}.

Answer 1

Answer:

L is not a regular language with formal proofs  

Explanation:

(a) To prove that L is not a regular language, we will use a proof by contradiction. the assumption entails  that L is a regular language. 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

(b) To determine that L is not a regular language, we mke use of proof by contradiction.  lets assume, that L is regular. Then by the Pumping Lemma for Regular Languages, it states also,

The pumping length, p for L such that for any string s ∈ L where |s| ≥ p, s = xyz subject  to the condtions as follows :

(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 is shown. by the first condition x and y are zeros.

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

It is shown that is is  not in L. This is a  contraption with the pumping lemma.  our assumption that L is regular is  incorrect, and L is not a regular language