(5 points) The collection of decidable languages is closed 1111(1er union: For a
ID: 654641 • Letter: #
Question
(5 points) The collection of decidable languages is closed 1111(1er union: For any two decidable languages L1 and L2. let M1 and M2 be the Turing machines that decide them. We construct a Turing machine M' that decides L1 U L2. M = ''On input u' 1. Run M on w. If it accepts, accept. 2. Run M2 on w. if it accepts, accept. Otherwise, reject.'' M' accepts if w if either M1 or M2 accepts it.. If both reject so does M'. In an analogous way, show that the decidable languages are closed concatenation. Hint: Consider all possible ways to split the original string into two consecutive strings.Explanation / Answer
Let L1 abd L2 be two Turning_machines and let M1 and M2 be TMs that recognizes L1 and L2 respectively.We construct a NTM N that recognizes L1 L2:on input w,
1. Nondeterministically split w into two parts w = xy.
2. Run M1 on x.If it rejects,halt output REJECT.If it accepts,go to Step3.
3. Run M2 on w.If it accepts,output ACCEPT.If it rejects,output REJECT.
If w belongs L1 L2,then there is a way to split w into two parts w = xy such that x belongs L1 and y belongs to L2,thus, M1 halts and accepts x,and M2 halts and accepts y.Hence at least one branch of N will accept w.On the other hand,if w doesnot belongs L1 L2,then for every possible splitting w = xy, x doesnot belongs to L1 or y doesnot belongs to L2,so M1 does not accept x or M2 does not accept y.Thus,all branch of N will reject w.Therefore, L(N) = L1 L2,and Turning languages are closed under concatenation.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.