Below is a faulty proof that L ab is not regular Play the r

Below is a faulty proof that L = a*b* is not regular. Play the role of grader: Identify any errors (by circling them) and explain and correct my misunderstanding of the pumping lemma. CLAIM: L = a*b* is not regular. \"PROOF\": For purposes of contradiction, suppose L is regular (so the pumping lemma for regular languages applies). Let p be the pumping length for L. Now consider w = aab^p. Clearly w elementof L and |w| = p + 2 greaterthanorequalto p, and we can write w as w = xyz as in the pumping lemma. Let x = a; y = ab; and z = b^p-1 (note that |xy| lessthanorequalto p as required by the pumping lemma). By the pumping lemma xy^2z = xyyz must also be in L. But xyyz = aababb^p-1 = aabab^p which is not in L (because all a\'s must be before all b\'s for any string in L) Thus, our initial assumption that L is regular be false, concluding the proof. Explain my misunderstanding of the pumping lemma (i.e., what the pumping lemma actually says vs. what I did).

Solution

In pumping lemma for regular languages , , Let L be a regular language. Then there exists a constant ‘c’ such that for every string w in L

|w| c

We can break w into three strings, w = xyz, such that

In your proof , you must have taken x and y values as strings of \"a\" andz as a combination of a and b . and retry the proof so that you can proove that L is not regular since it has to be of the form a^nb^n

At first, we have to assume that L is regular.

So, the pumping lemma should hold for L.

Use the pumping lemma to obtain a contradiction

Select w such that |w| c

Select y such that |y| 1

Select x such that |xy| c

Assign the remaining string to z.

Select k such that the resulting string is not in L.

|w| = 2n n.

By pumping lemma, let w = xyz, where |xy| n.

Let x = a^p, y = a^q, and z = a^rbⁿ, where p + q + r = n.p 0, q 0, r 0. Thus |y| 0

Let k = 2. Then xy²z = a^pa^2qa^rbⁿ.

Number of a s = (p + 2q + r) = (p + q + r) + q = n + q

Hence, xy²z = a^n+q bⁿ. Since q 0, xy²z is not of the form aⁿbⁿ.

Thus, xy²z is not in L. Hence L is not regular.