MadeEasy Subject Test: Theory of Computation - Identify Class Language

Question

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

• A. Regular
• B. CFL but not regular
• C. CSL but not CFL
• D. Recursive but not CSL

Comments

Given answer is CFL

---

https://cs.stackexchange.com/questions/307/show-that-xy-%e2%88%a3-x-y-x-%e2%89%a0-y-is-context-free?noredirect=1&lq=1

---

thanks @junaid for such a good link

Answer 1

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.

Comments

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 )^{*}$

right?

---

yes then regular for sure
chk this
https://gateoverflow.in/159564/cfl-or-csl

Answer 2

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

Comments

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?

https://cs.stackexchange.com/questions/307/show-that-xy-%e2%88%a3-x-y-x-%e2%89%a0-y-is-context-free?noredirect=1&lq=1

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.

Answer 3

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.

Comments

0110 is part of language but not generated by your grammar kindly check

Answer 4

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.

Comments

Your PDA is wrong as it accepts 1010 .