Part A

Let [tex]L_1[/tex] and [tex]L_2[/tex] be decidable languages and define [tex]L_3[/tex] as the set difference of the two, [tex]L_3 = L_1 \setminus L_2[/tex].

1. Prove that [tex]L_3[/tex] is decidable.
2. Does this change if [tex]L_1[/tex] is recognizable, and not decidable?
3. What if [tex]L_2[/tex] is recognizable, and not decidable?

Part B

A language [tex]L_1[/tex] can be concatenated with another language [tex]L_2[/tex] (denoted [tex]L_1 L_2[/tex]) as follows:

[tex]s \in L_1 L_2 \iff s = s_1 s_2[/tex] for some [tex]s_1 \in L_1[/tex] and some [tex]s_2 \in L_2[/tex].

Prove that if [tex]L_1[/tex] and [tex]L_2[/tex] are decidable then [tex]L_1 L_2[/tex] is decidable.

([tex]\overline{L_2}[/tex] is the complement of [tex]L_2[/tex].)

Part C

[tex]L_1 = \{\langle M, w \rangle \mid M \text{ rejects } w \text{ but accepts } w^r \}[/tex]

Note that [tex]w^r[/tex] is [tex]w[/tex] written in reverse, for example, if [tex]w = 1101[/tex] then [tex]w^r = 1011[/tex].

Show that [tex]L_1[/tex] is recognizable.

Part A: To prove that L3 is decidable when L1 and L2 are decidable, we need to show that there exists a Turing machine that can decide membership in L3.

Since L1 and L2 are decidable, there exist Turing machines M1 and M2 that can decide membership in L1 and L2, respectively.

To decide membership in L3, we can construct a Turing machine M3 as follows: M3 = "On input x: 1. Run M1 on x. If M1 accepts, go to step 2. Otherwise, reject. 2. Run M2 on x. If M2 accepts, reject. Otherwise, accept."

M3 simulates M1 and M2 on the input x. If M1 accepts x and M2 does not accept x, then x is in L3. Otherwise, x is not in L3.

Therefore, L3 is decidable.

If L1 is recognizable but not decidable, the decidable property of L2 does not affect the decidability of L3. L3 can still be decidable as long as there exists a Turing machine that can decide membership in L2.

If L2 is recognizable but not decidable, the decidability of L1 does not affect the decidability of L3. L3 can still be decidable as long as there exists a Turing machine that can decide membership in L1.

Part B: To prove that L1L2 is decidable when L1 and L2 are decidable, we need to show that there exists a Turing machine that can decide membership in L1L2.

Since L1 and L2 are decidable, there exist Turing machines M1 and M2 that can decide membership in L1 and L2, respectively.

To decide membership in L1L2, we can construct a Turing machine M as follows: M = "On input x: 1. Split x into two parts, s1 and s2. 2. Run M1 on s1 and M2 on s2. 3. If both M1 and M2 accept their respective inputs, accept. Otherwise, reject."

M splits the input x into two parts, s1 and s2, and runs M1 on s1 and M2 on s2. If both M1 and M2 accept their respective inputs, then x is in L1L2; otherwise, x is not in L1L2.

Therefore, L1L2 is decidable.

Part C: To show that L1 is recognizable, we need to demonstrate the existence of a Turing machine that recognizes L1.

We can construct a Turing machine M as follows: M = "On input ⟨M, w⟩: 1. Simulate M on w. 2. If M accepts w, go to step 3. Otherwise, continue. 3. Reverse the input w. 4. Simulate M on the reversed input w. 5. If M accepts the reversed input w, accept. Otherwise, continue."

M simulates the given Turing machine M on the input w. If M accepts w, it proceeds to reverse w and simulates M on the reversed input. If M accepts the reversed input, M accepts ⟨M, w⟩.

Therefore, L1 is recognizable.

In conclusion, we have shown that L3 is decidable when L1 and L2 are decidable, the decidability of L1L2 when L1 and L2 are decidable, and the recognizability of L1.

To know more about decidable , visit

https://brainly.com/question/33327692

#SPJ11