 Suggested languages for you:

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.
See the step by step solution

## Step 1: A. Proof for Union

Given decidable languages $$L_1$$ and $$L_2$$, we can construct a Turing Machine (TM) $$M$$ which decides $$L = L_1 \cup L_2$$. TM $$M$$ can be constructed by running TM $$M_1$$ for $$L_1$$ and TM $$M_2$$ for $$L_2$$ in parallel on the input $$w$$. If either $$M_1$$ or $$M_2$$ accepts, $$M$$ accepts. If both $$M_1$$ and $$M_2$$ reject, $$M$$ rejects. Hence, the language $$L_1 \cup L_2$$ is also decidable.

## Step 2: B. Proof for Complementation

Given a decidable language $$L$$, we can construct a TM $$M_L'$$ that decides the complement of $$L$$. TM $$M_L'$$ can be constructed by running the TM $$M_L$$ for $$L$$ and switching the accept and reject states. If $$M_L$$ accepts, $$M_L'$$ rejects and vice versa. Hence, the complement of $$L$$ is decidable.

## Step 3: C. Proof for Concatenation

If we are given two decidable languages $$L_1$$ and $$L_2$$, we can construct a Turing Machine $$M$$ that decides $$L = L_1 \cdot L_2$$. TM $$M$$ can be constructed by running TM $$M_1$$ for $$L_1$$ and TM $$M_2$$ for $$L_2$$ on all possible partitions (of $$w$$ into $$x$$ and $$y$$) in parallel. If $$M_1$$ accepts $$x$$ and $$M_2$$ accepts $$y$$, $$M$$ accepts $$w$$. Otherwise, $$M$$ rejects $$w$$. Thus, the language of $$L_1 \cdot L_2$$ is decidable.

## Step 4: D. Proof for Intersection

Given two decidable languages $$L_1$$ and $$L_2$$, we can construct a Turing Machine $$M$$ which decides $$L = L_1 \cap L_2$$. TM M can be constructed by running TM $$M_1$$ for $$L_1$$ and TM $$M_2$$ for $$L_2$$ in parallel on the input $$w$$. If both $$M_1$$ and $$M_2$$ accept, $$M$$ accepts. If either $$M_1$$ or $$M_2$$ rejects, $$M$$ rejects. Hence, $$L_1 \cap L_2$$ is decidable.

## Step 5: E. Proof for Star Operation

For a decidable language $$L$$, we construct a Turing machine $$M$$ which decides $$L^{*}$$, the set of all strings that can be made by concatenating zero or more strings from $$L$$. For an input string $$w$$, construct $$M$$ to enumerate over all the possible ways to split $$w$$ into substrings $$w_1, w_2, ..., w_k$$ and run the Turing machine $$M_L$$ for $$L$$ on all these substrings in parallel. If $$M_L$$ accepts all $$w_i$$, $$M$$ accepts $$w$$. If $$M_L$$ rejects any one of the $$w_i$$, $$M$$ rejects $$w$$. Thus, $$L^{*}$$ is decidable.

We value your feedback to improve our textbook solutions.

## Access millions of textbook solutions in one place

• Access over 3 million high quality textbook solutions
• Access our popular flashcard, quiz, mock-exam and notes features ## Join over 22 million students in learning with our Vaia App

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 