edited by
3,922 views
6 votes
6 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
edited by

7 Answers

3 votes
3 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.
3 votes
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

CFL$\cap$Regular=CFL

ans will be CFL

2 votes
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.
0 votes
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.

Related questions