The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

I don't think it will be regular .

Had the language been uww^{R}v 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.

*Notes on the Myhill-Nerode Theorem*

Now, come to the problem

Here L = { ww^{R}v | 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^{R}a 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^{R}a) != L (yx^{R}a)

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.

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.9k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 448
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

37,964 questions

45,466 answers

131,325 comments

48,379 users