Below is a faulty proof that L = a*b* is not regular. Play the role of grader: I

Question

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).

Explanation / Answer

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 = ap, y = aq, and z = arbn, where p + q + r = n.p 0, q 0, r 0. Thus |y| 0

Let k = 2. Then xy2z = apa2qarbn.

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

Hence, xy2z = an+q bn. Since q 0, xy2z is not of the form anbn.

Thus, xy2z is not in L. Hence L is not regular.

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.