The Gateway to Computer Science Excellence
+3 votes

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

  1. Regular
  2. CFL but not regular
  3. CSL but not CFL
  4. Recursive but not CSL
in Theory of Computation by (237 points)
edited by | 450 views
Question is confusing , what do they mean by x not equal to Y , but |x|=|y|.

Means the language xnyn. Here x!=y and we know that this language is CFL.

Given answer is CFL
thanks @junaid for such a good link

6 Answers

+3 votes

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


ans will be CFL

by Veteran (119k points)
Can we compare {xy / x != y} as complement of {ww/ w belongs to (a+b)*}.
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)
yes corrected now
@ srestha can we do like what @ Shubhanshu suggesting ?
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?
This DFA will also accept 11, 00, 0000, 1111, ...........

which violates the condition that x not equal to y.


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


ans will be CFL

what is ans @ junaid ahmad

I think final ans CFL and DCFL

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
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 checking if two halves of a string are not the same cant be CFL.

So its like CSL but not CFL.
@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.
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.

@Arjun Sir

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

But odd length of string will not contain here


Moreover complement of ww is also a CFL.

@Praveen Sir proved here

Am I correct [email protected] Sir confirm plz

@Hemant there is no wwr concept

The best way u can contradict with me

if u can give a string which doesnot satisfy my logic

take any and contradict :)

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

non equivalence of 2 string can be done in one stack? Can u give me an example of it?

here it is said , it is a case of nested induction

Can you give a PDA for  

L={xy∣x, y∈{0,1}∗ where x!=y but |x|=|y|}. As I am not able to understand how you will compare bottom of the stack with Y's symbols.
+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.
by Active (3.3k points)
But answer is given as CFL but not Regular Option(B)
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.
Detecting if two strings are "NOT EQUAL" can be done with NPDA.
@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 )^{*}$

yes then regular for sure
chk this
+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:





Hence, it is CFL.
by Active (1.3k points)
0110 is part of language but not generated by your grammar kindly check
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.

by Active (4.4k points)
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


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

by Boss (14.7k points)
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.
by (161 points)
here memory required
yes it si require because you want X!=Y, how without storing X you will know that it is not equla to Y, also you have to know length of it.
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
50,737 questions
57,391 answers
105,442 users