Question

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

Answer 1

Here is the solution:

Lemma not # Given 2= {v/v = vry &={a,by By using pumping we can prove the language is regular. If a language is Regular. L' and it has a 'P! such that any string 's' where Islap string can be divided into 3 parts s = xyz. must satisfy conditions : ayiz EL for every pumping length and the and it U2 iyo (2) Tylso (3) 1ay1 p. aiven lan language: L = of v/v = vez It means the language contains strings only palindromes ouer {a,by L={a,b, aba, bab, abba, 4 Anume that the language is regular language let p=4 string: aaaa baada 181>P ay Z

for condition 1

x y^i z belongs to L let i =2

then string will be

a aaaa abaaaa

underlined part is y^2

this string aaaaaabaaaa does not belongs to Given language

condition 1 is failed

condition 2 :

| y | >0

|aa|>0

2>0 true

condition 3

|x y |<=p

|aaa|<=4

3<=4 true

But for a regular language all conditions must satisfy here condition 1 is  not satisfied and It is contradiction to our assumption L is a regular language.

So Given L is not regular.

If you have any doubts please leave a comment!!!!!