Peter Linz Chapter 4.3 Exercise Q.20

Question

I don't think it will be regular .

Had the language been uww^Rv the expression could have been (a+b)*(aa+bb)(a+b)* as there is no restriction on w.

Is it correct? and if it isn't regular, is it a CFL?

Answer 1

Let us assume that if a string x belongs to a language L then L(x) = 1 otherwise L(x) = 0. Now, read the theorem written below

Myhill-Nerode Theorem: Let L ⊆ Σ* be any language. Suppose there is an infinite set S of strings such that for  

       (∀x != y ∈ S)(∃z ∈ Σ*) such that L(xz) != L(yz).

        Then L is not a regular language.

To understand the theorem completely go to the link below. I have taken the theorem from there.

 Notes on the Myhill-Nerode Theorem

Now, come to the problem 

Here L = { ww^Rv | v,w ∈ {a,b}⁺ }

As told in the Myhill - Nerode theorem above I am taking an infinite set S

Let S = { w | w ∈ {a,b}⁺ }

Now, we take arbitrary two strings x and y belongs to S (here x!=y)

Now, we will take an arbitrary string z ∈ Σ* such that  L(xz) != L(yz)

Let z= x^Ra then the string xz = xx^R a belongs to L that is L (xx^R a) = 1

but the string yz = yx^R a does not belong to L that is L (yx^R a) = 0

Hence, L (xx^Ra) !=  L (yx^Ra)

Thus for any two strings x and y belongs to an infinite set S there exist a string z ∈ Σ* such that L(xz) != L(yz) 

So, according to myhill nerode theorem we get L is not regular.

(If you are not getting what I have done then look at the examples done in the link above)

Yes the language is context - free because concatenation of context-free and regular is context-free.