Question

Prove that language Lon {a, b}, L={ vv = v*} is not regular.

Answer 1

Note:--> Do Upvote the answer if U like it and have any doubt comment it

We can prove any language Not regular by using Pumping Lemma

Pumping Lemma Definition

Let L be a regular language, recognized by a DFA with p states And Let x ∈ L with |x| ≥ p, there exists u, v, w ∈ Σ∗, such that x = uvw, and
(1) |uv| ≤ p
(2) |v| ≥ 1
(3) for all i ≥ 0: uvⁱw ∈ L

L = { ( a,b} * | v = v^R }

Lets See how we can proof That L is not Regular by contradiction To do so we need to find a string that is possible acc to  pumping lemma but not in L then we say L is not regular

Steps

1. We have a DFA for above language with states p

2. Now choose a x ∈ L such that it will contradict the lemma

3. So we take x = a^p  b a^p   so x  is a palindrome, so x∈L Also, |x| = 2p+1 ≥ p

According to given first two Condition we have

• u =a^k
• v=a^m
• w=a^p-m-k  b a^p

for some k , m >0 so that k+m ≤ p and m≥1

Now we need to show that for some values of i  uvⁱw ∈ L doesn't hold

Let take For example i = 2

u v v w = a^k a^m a^m a^p-m-k b a^p

= a^p+m b a^p -------- 1

Now Reverse of ( uvvw)^R = a^p  b a^{p +m} ------------ 2

From 1 and 2 we get

(uvvw) is not equal to ( uvvw)^R

Conclusion:-->Therefore uv²z ∉L So we saw that we have satisfies all three conditions But we get a uv^2w that doesn't belong to L So it contradict the Lemma

Hence we Say that L is not regular

So this is how we can prove any language is non regular

Thank You