### Select your language

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.

### Short Answer

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

## Unlock all solutions

Get unlimited access to millions of textbook solutions with Vaia Premium

Over 22 million students worldwide already upgrade their learning with Vaia!

## 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.

What do you think about this solution?

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
• Access our smart AI features to upgrade your learning

## 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