Use the pumping lemma to show that the following language is nonregular: L={a^i

Question

Use the pumping lemma to show that the following language is nonregular:

L={a^i b^j c^k ;|i+j=k, i,j,k>=0}. Please show complete proof.

Explanation / Answer

Let L be a^i b^j c^k for i+j=k and i,j, k >= 0. We use the Pumping Theorem to show that L is not regular. If it were, then there is some k for which any string w such that w >=k satisfies the conditions of the Pumping Lemma. Let w = a^k b^k c^2k. |w| = 4y, and so |w| >= k, satisfying the conditions for the Pumping Lemma. There must exist x, y, and z such that w = xyz, |xy| = 0, x y^q z is in L. We show that no x, y, and z exist. Let y = a^p for some p. Since y =/= epsilon, p must be greater than 0. Let p = 2. We now have a^(k + 1) b^k c^2k. Pumping Lemma says that this string must in L, but this string isn't in L since i + j = k but (k + 1 ) + k =/= 2k. Therefore, at least one string in L fails to satisfy the Pumping Lemma. So L = a^i b^j c^k for i+j = k and i, j, k >= 0 is not regular.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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