edited by
3,930 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

0 votes
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
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.
0 votes
0 votes
**Claim**: $L$ is context-free.

**Proof Idea**: There has to be at least one difference between the first and second half; we give a grammar that makes sure to generate one and leaves the rest arbitrary.

**Proof**: For sake of simplicity, assume a binary alphabet $\Sigma = \{a,b\}$. The proof readily extends to other sizes. Consider the grammar $G$:

$\qquad\begin{align}
  S &\to AB \mid BA \\
  A &\to a \mid aAa \mid aAb \mid bAa \mid bAb \\
  B &\to b \mid aBa \mid aBb \mid bBa \mid bBb
\end{align}$

It is quite clear that it generates

$\qquad \mathcal{L}(G) = \{ \underbrace{w_1}_k x \underbrace{w_2v_1}_{k+l}y\underbrace{v_2}_l \mid |w_1|=|w_2|=k, |v_1|=|v_2|=l, x\neq y \} \subseteq \Sigma^*;$

the suspicious may perform a nested induction over $k$ and $l$ with case distinction over pairs $(x,y)$. Now, $w_2$ and $v_1$ commute (intuitively speaking, $w_2$ and $v_1$ can exchange symbols because both contain symbols chosen independently from the rest of the word). Therefore, $x$ and $y$ have the same position (in their respective half), which implies $\mathcal{L}(G) = L$ because $G$ imposes no other restrictions on its language.

---

Related questions