Instructions
This problem set is due on Wednesday March 11, 2020 at 18:00, to be submitted on Gradescope. Each problem is worth 10 marks in total.
Problems
- Last week, you showed that for a context-free grammar $G$ and a regular expression $R$, the problem of whether $L(G) \subseteq L(R)$ is decidable. Show that $L(R) \subseteq L(G)$ is undecidable.
Note. We will prove these later, so you can use the fact that containment, equality, and universality of context-free languages is undecidable.
- Consider the language
$$L = \{\langle M,N \rangle \mid \text{$M$ and $N$ are Turing machines and $L(M) \cap L(N) \neq \emptyset$}\}.$$
- Show that $L$ is recognizable.
- Show that $L$ is undecidable.
- Consider the following languages,
- $L_1 = \{\langle M,n \rangle \mid \text{$\exists x \in \Sigma^*$ such that $M$ halts on input $x$ within $n$ steps }\}$,
- $L_2 = \{\langle M,n \rangle \mid \text{$\exists x \in \Sigma^*$ such that $M$ halts on input $x$ and $|x| = n$ }\}$,
where $M$ is a Turing machine and $n$ is an integer.
One of these languages is decidable and the other is not. Determine which language is decidable and which is undecidable. Give proofs for both.
Reflection
This is the final problem set and the final reflection. This is meant to give you an opportunity to reflect back on your learning in the course. As usual, I will be reading and responding to your submissions.
Completion of this part is optional but is worth an extra 10 marks in total and will be loosely graded on completion/thoughtfulness and not "correctness" (i.e. what you think I want you to say); you should aim for about a paragraph or two of "thoughtfulness".
- Did anything go wrong for you in the course? What things went right? Did anything surprise you? If you had to take this course again, would you change anything in how you approached it?
- What would you say are the big ideas of this course? How would you explain it to someone who hasn't taken it or is thinking about taking it?
- What are your takeaways from this course? Have you gotten what you wanted out of this course?
- Is there anything else you'd like to conclude with?