105 views

I don't think it will be regular .

Had the language been uwwRv 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?

+1 vote

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.

Now, come to the problem

Here L = { wwRv | 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= xRa then the string xz = xxR a belongs to L that is L (xxR a) = 1

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

Hence, L (xxRa) !=  L (yxRa)

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.

edited

1