Prove that the following language is not regular aibaj i

Prove that the following language is not regular: { aⁱba^j | i >= 2j >= 0 } SHOW ALL WORK, THANKS!

Solution

Given language aibaj |i>=2j>=0

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

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.

Hence L is not regular.

Here , we are given a^iba^j | i>=2 j>=0

At first, we assume that L is regular and n is the number of states.

Let w = aⁿbⁿ. Thus |w| = 2n n.

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

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

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

Number of as = (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.