CMSC 28000 — Problem Set 7

Instructions

This problem set is due on Wednesday March 4, 2020 at 18:00, to be submitted on Gradescope. Each problem is worth 10 marks in total.

Problems

1. We say a word $u = a_1 \cdots a_k$ is a scattered subword of $v$ if $v \in \Sigma^* a_1 \Sigma^* a_2 \Sigma^* \cdots \Sigma^* a_k \Sigma^*$. For example, $thinly$ is a scattered subword of $otorhinolaryngology$. Describe a Turing machine that accepts the language $$L = \{u \# v \mid \text{$u$ is a scattered subword of $v$} \}.$$
2. Consider a $k$-track Turing machine. The machine is like an ordinary Turing machine, but has $k$ tapes and a single tape head which reads all tapes at once and performs a transition based on what it reads.
   1. Describe how to simulate a $\ell$-tape Turing machine with a $k$-track Turing machine.
   2. Describe how to simulate a $k$-track Turing machine with an ordinary Turing machine.
3. Let $G$ be a context-free grammar and let $R$ be a regular expression. Consider the following problems.
   • Is $L(G) \subseteq L(R)$?
   • Is $L(R) \subseteq L(G)$?
   One of these problems is decidable and the other is not. Determine which of these problems is decidable and prove why.