# Is {< M >| L(M) ∩ (ab)∗ is infinite} in D, SD/D, or not in SD?

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.

$$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?
• 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. – David Richerby Dec 8 '17 at 19:54
• @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.) – David Richerby Dec 8 '17 at 20:10
• @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$. – David Richerby Dec 8 '17 at 20:12