Suggested languages for you:

Americas

Europe

Problem 15

Show that the collection of decidable languages is closed under the operation of A. union. d. complementation. b. concatenation. e. intersection. c. star.

Expert verified

The collection of decidable languages is closed under the operation of union, complementation, concatenation, intersection, and star. Given decidable languages \(L_1\) and \(L_2\), we can construct Turing Machines which decide \(L_1 \cup L_2\), \(L_1^C\), \(L_1 \cdot L_2\), \(L_1 \cap L_2\), and \(L^*\) respectively, by running the input through TMs for individual languages in parallel and modifying the acceptance conditions accordingly. Thus, the resulting languages are also decidable.

What do you think about this solution?

We value your feedback to improve our textbook solutions.

- Access over 3 million high quality textbook solutions
- Access our popular flashcard, quiz, mock-exam and notes features
- Access our smart AI features to upgrade your learning

Chapter 3

In Theorem \(3.21\), we showed that a language is Turing-recognizable iff some enumerator enumerates it. Why didn't we use the following simpler algorithm for the forward direction of the proof? As before, \(s_{1}, s_{2}, \ldots\) is a list of all strings in \(\Sigma^{*}\). \(E={ }^{*}\) Ignore the input. 1\. Repeat the following for \(i=1,2,3, \ldots\) 2\. Run \(M\) on \(s_{i}\). 3\. If it accepts, print out \(s_{i} . "\)

Chapter 3

Give implementation-level descriptions of Turing machines that decide the following languages over the alphabet \(\\{0,1\\}\). A a. \(\\{w \mid w\) contains an equal number of 0 and 1 s \(\\}\) b. \(\\{w \mid w\) contains twice as many 0 s as 1 s \(\\}\) c. \(\\{w \mid w\) does not contain twice as many \(0 \mathrm{~s}\) as $1 \mathrm{~s}\\}$

Chapter 3

Examine the formal definition of a Turing machine to answer the following questions, and explain your reasoning. a. Can a Turing machine ever write the blank symbol \(\lrcorner\) on its tape? b. Can the tape alphabet \(\Gamma\) be the same as the input alphabet \(\Sigma\) ? c. Can a Turing machine's head ever be in the same location in two successive steps? d. Can a Turing machine contain just a single state?

Chapter 3

Let \(c_{1} x^{n}+c_{2} x^{n-1}+\cdots+c_{n} x+c_{n+1}\) be a polynomial with a root at \(x=x_{0}\). Let \(c_{\max }\) be the largest absolute value of a \(c_{i}\). Show that $$ \left|x_{0}\right|<(n+1) \frac{c_{\mathrm{max}}}{\left|c_{1}\right|} $$

Chapter 3

(a) For any two decidable languages \(L_{1}\) and \(L_{2}\), let \(M_{1}\) and \(M_{2}\) be the TMs that decide them. We construct a $\operatorname{TM} M^{\prime}\( that decides the union of \)L_{1}\( and \)L_{2}$ : "On input w: 1\. Run \(M_{1}\) on \(w\). If it accepts, accept. 2\. Run \(M_{2}\) on \(w\). If it accepts, accept. Otherwise, reject." \(M^{\prime}\) accepts \(w\) if either \(M_{1}\) or \(M_{2}\) accepts it. If both reject, \(M^{\prime}\) rejects.

The first learning app that truly has everything you need to ace your exams in one place.

- Flashcards & Quizzes
- AI Study Assistant
- Smart Note-Taking
- Mock-Exams
- Study Planner