1
$\begingroup$

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

$\endgroup$

2 Answers 2

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – venkat
    Commented Jan 7, 2018 at 13:56
  • $\begingroup$ You can prove the undecidability of $L$ by other means, e.g. the Rice Theorem. $\endgroup$
    – quicksort
    Commented Jan 7, 2018 at 15:17
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.