Classification of the complement of a language - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-10-20T00:34:11Z https://cs.stackexchange.com/feeds/question/86399 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/86399 0 Classification of the complement of a language venkat https://cs.stackexchange.com/users/80805 2018-01-07T12:32:05Z 2018-01-07T14:21:07Z <p>$L = \{ \langle M \rangle \mid M \text{ accepts two strings of different lengths} \}$.</p> <p>What is complement of this language?</p> <p>my attempt:</p> <p>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?</p> https://cs.stackexchange.com/questions/86399/-/86400#86400 1 Answer by quicksort for Classification of the complement of a language quicksort https://cs.stackexchange.com/users/62447 2018-01-07T13:12:34Z 2018-01-07T13:12:34Z <p>The complement of $L$ is:</p> <p>$\bar{L} = \{\langle M \rangle \mid \text{ all strings accepted by$M$have the same length} \}$</p> <p>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).</p> https://cs.stackexchange.com/questions/86399/-/86403#86403 0 Answer by fade2black for Classification of the complement of a language fade2black https://cs.stackexchange.com/users/72943 2018-01-07T14:21:07Z 2018-01-07T14:21:07Z <p>The complement of $L$ is $$\overline{L} = \{\langle M \rangle \mid |L(M)|&gt;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.</p> <p>$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.</p>