Are these languages in D, SD/D, or not in SD?

$$L_1 = \{\langle M \rangle\mid L(M)\cap (ab)^*\text{ is infinite}\}$$

I kind of understand decidability and undecidability problems, but the "$\cap(ab)^*$" here threw me off a little. but I'm thinking that maybe I should deal with this as if it's just $L(M)$ basically since the intersection of a regular language with an arbitrary language could be anything; in other words, reduce $\neg H = \{\langle M, w\rangle\mid \text{TM }M\text{ does not halt on }w\}$ to $L_1$, and conclude that there isn't a machine to semi-decide $\neg H$, so $L_1$ is not in SD.

So basically, since $(ab)^*$ is infinite, we could run $L(M)$ on an infinite $(ab)^*$ string, but since it may never halt and accept, this language is not even semi-decidable.

What about

$$L_2 = \{\langle M \rangle\mid L(M) \cap (ab)^∗ \neq\emptyset\}\,?$$

If my idea of intersection is right, I believe that this is in SD\D (Turing enumerable, but not decidable), and that can be proven by reducing $A = \{\langle M\rangle\mid L(M)\neq\emptyset\}$ to $L_2$. Does this sound right?

  • $\begingroup$ There's no such thing as "an infinite $(ab)^*$ string" -- strings are finite by definition. Also, although it's true that the intersection of an arbitrary language with a regular language could be a language of any class, that doesn't tell you much about the intersection of a specific language ($L(M)$) with a specific regular language ($(ab)^*$). That can't be literally "anything", since it consists only of strings with alternating $a$s and $b$s. $\endgroup$ – David Richerby Dec 8 '17 at 19:54
  • $\begingroup$ @DavidRicherby so then it could either be the empty set, if L(M) = the complement of (ab)*, or any class of language that is a subset of (ab)*? $\endgroup$ – my name is python Dec 8 '17 at 19:59
  • $\begingroup$ @DavidRicherby "strings are finite by definition". We do have infinite length strings, don't we? We have had similar discussion a couple days ago, "countably infinite strings". They are also by definition. $\endgroup$ – fade2black Dec 8 '17 at 20:04
  • $\begingroup$ @fade2black Sure, but when somebody is talking about inputs to Turing machines and is writing things like "$(ab)^*$, and says just "string" rather than some variant of "infinite string" then the strings under discussion are finite. (Unless it's explicitly stated that we're considering infinite inputs to TMs, which would be unusual.) $\endgroup$ – David Richerby Dec 8 '17 at 20:10
  • $\begingroup$ @mynameispython Yes, the intersection of something with $(ab)^*$ is always a (possibly empty) subset of $(ab)^*$. (And, more generally, it's always true that $X\cap Y\subseteq Y$. $\endgroup$ – David Richerby Dec 8 '17 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.