Prove that the class of Turing-recognizable languages is closed under the dagger

Question

Prove that the class of Turing-recognizable languages is closed under the dagger operation.

Define the unary language operation called dagger on any arbitrary language L as follows. If L has alphabet sum = { sigma 1, sigma 2, ?, sigma k}, then L = { w |w E sigma* and at least one E L }. For example, suppose E = {a,b}. Then if L1 = {aba,aaaa}, we have L1 = sumsumsumsumsum. Furthermore, if L2 = {aa,bbb,abab}, then L = sum sum U sumsumsum. Prove that the class of Turing-recognizable languages is closed under the dagger operation.

Explanation / Answer

Solution:

Consider L1 and L2 be two Turing recognizable languages.

M1 and M2 are Turing machines that recognize L1 and L2 respectively.

Construct the NonTuring machine M that recognizes as L1 and L2 and output in the

form of w.

Step 1: Split the Turing machine w into two parts as w = xy

Step 2: Turing machine M1 Run on x.

                        If accepts it will go to the step 3 otherwise it will display result as REJECT.

Step 3: Turing machine M2 Run on x.

                        If accepts it will display the result as ACCEPT otherwise it will display result as REJECT.

If w€L1L2 then there always split w into 2 parts w = xy such that x€L1 and y€L2 then M1 halts and accepts x and M2 accepts y.

That means at least one branch of N that will accept w.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.