Question

Use pumping lemma to prove that L3a = {ab^m ab^m a| m>0} is non-regular

Answer 1

ab^n ab^n a

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.

Thus =================================================

1. At first, we assume that L is regular and n is the number of states.Let w = ab^n ab^n a . Thus |w| = 2n ≥ n.
2. By pumping lemma, let w = xyz, where |xy| ≤ n.
3. Let x = ab^p, y = ab^q, and z = a, where p + q + r = n, p ≠ 0, q ≠ 0, r ≠ 0. Thus |y| ≠ 0
4. Let k = 2. Then xy²z = ab^p ( ab^q )^2  a
5. Number of as = (p + 2q ) = (p + q ) + q = n + q
6. Hence, xy²z = a^n+q bⁿ. Since q ≠ 0, xy²z is not of the form  ab^n ab^n
7. Thus, xy²z is not in L. Hence L is not regular.