The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes

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?

asked in Theory of Computation by Junior (643 points) | 78 views

1 Answer

+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.

 Notes on the Myhill-Nerode Theorem

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.

answered by Loyal (8.1k points)
edited by

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,964 questions
45,466 answers
48,379 users