Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
If you could include your thought process in determining why it's regular it would help me a lot.
$L_1 = (0^*(10)^*11)$
$L_2 = \{ \langle M \rangle \mid M \text{ is a Turing machine that halts on all inputs from }L_1 \}$
$L_3 = \{ x \in \{0,1\}^* \mid \exists y \in L_2. xy \in L_1 \}$
Why is $L_3$ regular? It's a set of strings, I need to determine if there's a DFA that can accept it. Do I even care about $L_2$ and $L_1$ in this case?
Short answer. The language $L_1$ is clearly regular. Further, $L_3 = L_1L_2^{-1}$ is a quotient of $L_1$ and hence it is regular since the quotient of a regular language by any language (regular or not) is regular. So you don't care about $L_2$, but you do care about $L_1$.
More details. Let $L$ and $R$ be languages. Then $LR^{-1} = \{ u \in A^* \mid ur \in L \text{ for some }r \in R\}$. Therefore $LR^{-1} = \bigcup_{r \in R} Lr^{-1}$. If $L$ is regular, there are only finitely many languages of the form $Lr^{-1}$, each of which is regular (this is the dual form of Nerode's lemma) and hence $LR^{-1}$ is a finite union of regular languages and thus it is regular.
Consider these regular languages: $$ R_1 = \begin{cases} 0^* & \exists_{m,n \in \mathbb{N}} 0^m(10)^n11 \in L_2 \\ \emptyset & \text{otherwise} \end{cases} \\ R_2 = \begin{cases} 0^*(10)^* & \exists_{n \in \mathbb{N}}(10)^n11 \in L_2 \\ \emptyset & \text{otherwise} \end{cases} \\ R_3 = \begin{cases} 0^*(10)^*1 & 011 \in L_2 \\ \emptyset & \text{otherwise} \end{cases} \\ R_4 = \begin{cases} 0^*(10)^* & 11 \in L_2 \\ \emptyset & \text{otherwise} \end{cases} \\ R_5 = \begin{cases} 0^*(10)^*1 & 1 \in L_2 \\ \emptyset & \text{otherwise} \end{cases} $$
Well, each of $R_i$ are regular and it is obvious that $L_3 = R_1 \cup R_2 \cup R_3 \cup R_4 \cup R_5$. Thus $L_3$ is also regular.
Note that the exact value of $R_i$ does not need to be known, and indeed will not be unless we have sufficient information about $L_2$.
Notice that $xy \in L_1$ implies that $x$ is prefix of a word in $L_1$. But all $L_1$'s prefixes are of the form $A = 0^*(10)^*$ or $B = 0^*(10)^*1$.
Then, because you don't give any constraint on the encoding of Turing Machine, I can set that $\langle M \rangle = 1, \langle M'\rangle = 11$, where $M$ and $M'$ are Turing machines that stop on every input.
Hence, $L_3$ is exactly $A \cup B$, and is thus regular.
But again, this is true only if you can chose the encoding of Turing Machine. Otherwise, it would depend on the way Turing Machine are encoded.
