1
$\begingroup$

Given a language $L\subseteq \Sigma^*$ in $P$, is the language

$subwords(L) = \{v\in\Sigma^* : \text{there exist } u,w\in \Sigma^* \text{ with } uvw\in L\}$

that consists of all subwords of words in $L$ also guaranteed to lie in $P$?

$\endgroup$

closed as unclear what you're asking by Raphael Mar 21 '14 at 21:13

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ What do you think? What have you tried? Where did you get stuck? $\endgroup$ – Yuval Filmus Mar 21 '14 at 13:12
  • $\begingroup$ This is a dump of an exercise problem, not a question. If you have a specific question regarding the wording of the problem or concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See also here for our homework policy, and here for a relevant discussion. You may also want to check out our reference questions. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Mar 21 '14 at 21:12
1
$\begingroup$

Hint: Let $L$ be the language consisting of a description of a Turing machine (bounded by $\#$ on both sides) followed by a terminating computation (both description and computation are over $\{0,1\}$). What is the language $\mathit{subwords}(L) \cap \#\Sigma^*\#$?

$\endgroup$
  • $\begingroup$ Thanks for the example. So subwords(L) is generally not even decidable. $\endgroup$ – Dave Mar 21 '14 at 14:27

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