# Classification of the complement of a language

$L = \{ \langle M \rangle \mid M \text{ accepts two strings of different lengths} \}$.

What is complement of this language?

my attempt:

the complement is: $M$ accepts no two strings of same length and this can be done by dovetailing different inputs on M but we can never say IT CANNOT ACCEPT TWO STRING OF SAME LENGTH and hence its NOT RECURSIVELY ENUMERABLE?

## 2 Answers

The complement of $L$ is:

$\bar{L} = \{\langle M \rangle \mid \text{ all strings accepted by$M$have the same length} \}$

Your intuition that $\bar{L}$ is not recursively enumerable is correct, it is in fact complete for $\Pi^0_1$ by reduction from the emptiness problem. If you only need to prove that $\bar{L}$ is not in $\textsf{RE}$, it is sufficient to observe that $L$ is undecidable (reduction from the halting problem) but $\textsf{RE}$ (trivial).

• yes i think the complement can be derived from propositional logic ]x ]y (accept(M,x,y) AND length(x)!=length(y)) of the above statement thanks, brother i don't actually have the knowledge of reductions :( ]-->there exists symbol – venkat Jan 7 '18 at 13:56
• You can prove the undecidability of $L$ by other means, e.g. the Rice Theorem. – quicksort Jan 7 '18 at 15:17

The complement of $L$ is $$\overline{L} = \{\langle M \rangle \mid |L(M)|>1 \implies \text{ all strings of } L(M) \text{ have the same length}\}$$ In words, $L$ consists of those TM $M$ such that either $L(M) = \emptyset$, or $L(M)$ has only one string, or all strings in $L(M)$ have the same length.

$L$ is recursively enumerable. Given $\langle M \rangle$ you can use dovetailing to search for two strings in $L(M)$ of different length, and accept $\langle M \rangle$ as soon as you find a single pair. You can solve yourself if $\overline{L}$ is recursively enumerable or not.