# Why is this language regular?

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.