Lecture 35
Section outline
-
January 10th, Wednesday (14:30-16:30)
Exercises
- Recall that for two strings \( x,w \in \Sigma^\ast \), we say that \(x\) is an infix of \(w\) if we can write \(w = uxv\) for some strings \( u,v \in \Sigma^\ast \). Define \({\cal P} = \{ L \; | \; L \in {\rm RE},\) every string in \( L \) has infix \( 01110\}\) and define \( L_{\cal P} = \{ \mathsf{enc}(M) \; | \; L(M) \in {\cal P} \} \).
- Use Rice's theorem to show that \(L_{\cal P}\) is not a recursive language
- Prove that \(L_{\cal P}\) is not in RE
- For a language \(L\) over \(\Sigma\), let \({\sf pref}(L) = \{ w \; | \; wx \in L, \; w \in \Sigma^\ast, \; x \in \Sigma^+ \}\). State whether RE is closed under the operator \({\sf pref}\) (exercise 3.7 from the Exercise collection)
- Assess whether the following languages are in RE (exercise from final exam of September 13th, 2019):
- \(L_1 = \{ enc(M, M') \; | \; L(M) \cup L(M') = \emptyset \}\)
- \(L_2 = \{ enc(M, M') \; | \; L(M) \cup L(M') \neq \emptyset \}\)
- Recall that for two strings \( x,w \in \Sigma^\ast \), we say that \(x\) is an infix of \(w\) if we can write \(w = uxv\) for some strings \( u,v \in \Sigma^\ast \). Define \({\cal P} = \{ L \; | \; L \in {\rm RE},\) every string in \( L \) has infix \( 01110\}\) and define \( L_{\cal P} = \{ \mathsf{enc}(M) \; | \; L(M) \in {\cal P} \} \).