Question

Let L = {x = a r b s c t | r + s = t, r, s, t ≥ 0}. Give the simplest proof you can that L is not regular using the pumping lemma.

Answer 1

Given Language L = { a^r b^s c^t | r+s=t ,r,s,t >=0 }

Pumping Lemma states that

For any language L, there exists an integer n, such that for all x ∈ L with |x| ≥ n, there exists u,v, w ∈ Σ*, such that x = uvw, and
(1) |uv| ≤ n
(2) |v| ≥ 1
(3) for all i ≥ 0: uv^ⁱw ∈ L

To prove that the language is not regular we have show that there exist alteast one string such that it is not in the language (i.e it has to fail pumping lemma Test

Let X=abc² ∈ L (r=s=1 and t=2) where the pumping length =3

we are spilting X into u ,v ,w such u = a, v = b and w = c²

it satisfies all the conditions of the pumping lemma so it string which belong the language L

(  uv^ⁱw when i=0 i.e string will be 'ab' also belongs to the language)

so here we will be pumping the v and see whether the obtained string is in language or not

if we find atleat one string which is not the language after pumping v then is the language won't be regular

uv^ⁱw when i=2 i,e string is ab²c² doesn't belong to language because it fails satisy the r+s=t so the string is not in the language

so we tell that the given language L is not Regular

Hope it is helpful for you. If so please upvote and for any queries please drop a comment :-)