2
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.