The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

Redirected from merged question 159564
Close

+1 vote

Consider the following language,

$L= \big\{ xy \mid x, \ y \in \big\{0,1\big\}^{*} \ where \ x \neq y \ but \ |x| = |y| \big\}$

The language is ___________.

- Regular
- CFL but not regular
- CSL but not CFL
- Recursive but not CSL

+2 votes

To implement this language, we need a machine which can detect strings of form L = {WW | W belongs-to {0,1}*} and reject such strings. This can be done using a LBA.

Hence answer should be CSL but not CFL.

It is not regular because we can't compare x and y using DFA

It is not CFL because we can't detect if X = Y and reject such strings. e.g 110110

It is CSL and hence Recursive too.

Hence answer should be CSL but not CFL.

It is not regular because we can't compare x and y using DFA

It is not CFL because we can't detect if X = Y and reject such strings. e.g 110110

It is CSL and hence Recursive too.

0

Bro, gave you the reason and example string. Language can't be accepted by PDA. We need LBA to make sure X is not equal to Y.

+1

@arjun sir if the question would be

$L=\left \{ xy \,\,|\, z,y\,\,\epsilon \left ( 0+1 \right )^{*}\,\text{and} \,\left | x \right | =\left | y \right |\right \}$

the it will be regular .right?

It will be Language accepting even length string.

reg exp=$L=\left ( \left ( 0+1 \right ) \left ( 0+1 \right ) \right )^{*}$

right?

$L=\left \{ xy \,\,|\, z,y\,\,\epsilon \left ( 0+1 \right )^{*}\,\text{and} \,\left | x \right | =\left | y \right |\right \}$

the it will be regular .right?

It will be Language accepting even length string.

reg exp=$L=\left ( \left ( 0+1 \right ) \left ( 0+1 \right ) \right )^{*}$

right?

+2 votes

In this question, it means that x should have the same length as y, but their content should be different.

Now, this can't be regular as we can't compare the length of x and y in there.

But using a CFG we can implement it as:

S->XY|YX

X->AXA|0

Y->AYA|1

A->0|1

Hence, it is CFL.

Now, this can't be regular as we can't compare the length of x and y in there.

But using a CFG we can implement it as:

S->XY|YX

X->AXA|0

Y->AYA|1

A->0|1

Hence, it is CFL.

+1 vote

**Ans A)**

As there is no match between x and y element, and we could tell **no of element in x= no of elements in y**

So, we we can tell it is an **even digit string**

Other than this we cannot assume anything

So, it should be a regular language of even length

NFA should be like this

$S->1S0 | 0S1|\epsilon$

**no of element in x= no of elements in y** that part is regular

x!=y this part is CFL

Concatenation of this two will be give ans

CFL$\cap$Regular=CFL

ans will be CFL

0

i Think it will be CSL eg: 01110101 x:0111 y:0101 how can we compare top most stack with bottom most stack element(What to push what to pop)

+1

when both x and y are lambda (string of length zero), x = y and hence this shouldn't be accepted but this DFA will accept it. Isn't it?

+1

This DFA will also accept 11, 00, 0000, 1111, ...........

which violates the condition that x not equal to y.

which violates the condition that x not equal to y.

+1

yes

that is why ans should be CFL ,I think

$S->1S0 | 0S1|\epsilon$

**no of element in x= no of elements in y** that part is regular

x!=y this part is CFL

Concatenation of this two will be give ans

CFL$\cap$Regular=CFL

ans will be CFL

what is ans @ junaid ahmad

I think final ans CFL and DCFL

0

Well I am just guessing that it should be CSL. Reason being:

L={xy|x, y∈{0,1}* where x=y}

is a Context sensitive language and its closed under its complement. $x\neq y$ , which is its complement should also be a CSL. And with regards to second condition that can be checked even by a stack so a CFL which in fact is a subset of CSL.

So It might be CSL. Correct me if I am wrong @srestha

L={xy|x, y∈{0,1}* where x=y}

is a Context sensitive language and its closed under its complement. $x\neq y$ , which is its complement should also be a CSL. And with regards to second condition that can be checked even by a stack so a CFL which in fact is a subset of CSL.

So It might be CSL. Correct me if I am wrong @srestha

0

see CSL is always correct ans

but u have to see more

if it is CFL or not CFL

that will give final ans

but u have to see more

if it is CFL or not CFL

that will give final ans

+2

@srestha x != y is not a part of CFL. You put all the elements of x into the stack. Now starting element of x (which is at the bottom) has to be matched with the first element of y. Which can't be done using only stack.

w != $w^{r}$ This is the part of CFL.

w != $w^{r}$ This is the part of CFL.

+2

Considering only even length strings, the given language contains the complement of $ww$. Those following standard resources for TOC should answer this staight away because this is an example given in the book.

0

@Arjun Sir

complement of ww contains $\left \{ \epsilon ,0,1,01,011,........ \right \}$

But odd length of string will not contain here

rt?

Moreover complement of ww is also a CFL.

https://gateoverflow.in/43562/toc

@Praveen Sir proved here

Am I correct [email protected] Sir confirm plz

@Hemant there is no ww^{r} concept

The best way u can contradict with me

if u can give a string which doesnot satisfy my logic

take any and contradict :)

+2

Answer is CFL -- but the method you used is wrong. CFL intersection Regular is CFL -- but it may or may not be regular. Also, in answers you should use the terms properly -- you cannot use concatenation in place of intersection or vice versa. These little things eventually separate toppers from others.

0

ok , thank u :)

but x!=y is the basic problem of this question

it might be string might be 10011111

where x=1001 y=1111

then no CFL and also no CSL satisfy it

what is the meaning of x!=y

Is it mean (1)each part of x different from y or

(2)total x string is different from y string

if (1) is case then S->0S1|1S0|epsilon makes string CFL

if 2 is case, it will be recursive but not CSL too

Am I right?

but x!=y is the basic problem of this question

it might be string might be 10011111

where x=1001 y=1111

then no CFL and also no CSL satisfy it

what is the meaning of x!=y

Is it mean (1)each part of x different from y or

(2)total x string is different from y string

if (1) is case then S->0S1|1S0|epsilon makes string CFL

if 2 is case, it will be recursive but not CSL too

Am I right?

+2

x != y

Simply means x is not equal to y. i.e., Any part of x and y makes them different. And checking equivalence of two strings cannot be done by a CFL, but checking the non-equivalence of two strings can be done by a CFL (NCFL). This is an example for complement of CFL being not CFL.

Simply means x is not equal to y. i.e., Any part of x and y makes them different. And checking equivalence of two strings cannot be done by a CFL, but checking the non-equivalence of two strings can be done by a CFL (NCFL). This is an example for complement of CFL being not CFL.

0 votes

Ans is Non Deterministic CFL hence CFL but not regular(cannot compare length).

It NCFL because, all "x" can be pushed onto stack, when "y" starts we can pop the elements from stack. This popping of stack is not known, hence it is NCFL, if we know when to push and Pop onto stack, then we can say it is an DCFL (Deterministic).

Correct me if iam wrong.

0 votes

This is clearly a CFL .

Actually if we focus , in the givel language he gave us the complement of language WW

I am reinterpreting this language here

L=(L1)'∩L2

L1=*{WW , W∈(0,1)∗} *

*L2= (XY, X,Y ∈(0,1∗ and |X|=|Y| ) )*

*we know complement of WW is CFL (Although WW is CSL) so (L1)'= CFL *

*L2 is clearly Regular language(Even length language).*

*CFL ∩ Regular = CFL *

0 votes

This is very crystal claer rule that whenever some comparison or memory requirement is there in gammer, it is not regular because FSM can neither store so nor remember. Here in this example, It is not regular as Length of X need to be remember as pattern as well.

It can not be CFL also as using stack you can not check wthere first alphabet of X is same as Y, because you have to pop enitre stack to know. Once you pop how you will check for rest.

Most probably it is CSL only.

It can not be CFL also as using stack you can not check wthere first alphabet of X is same as Y, because you have to pop enitre stack to know. Once you pop how you will check for rest.

Most probably it is CSL only.

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.8k
- Digital Logic 2k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.8k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 941
- Others 1.2k
- Admissions 334
- Exam Queries 410
- Tier 1 Placement Questions 17
- Job Queries 52
- Projects 8

34,239 questions

40,932 answers

116,230 comments

39,846 users