1 answer

4. Given two languages A and B, show that if An B and AUB are decidable,...

Question:

4. Given two languages A and B, show that if An B and AUB are decidable, then A is decidable.

4. Given two languages A and B, show that if An B and AUB are decidable, then A is decidable.

Answers

Let M and N be the decidable Turing machine for first and second decidable language given above respectively .

Now the membership for A can be decided for all 4 possible cases as follows :-

1. If input x is in A and B as well.

In this case, M will accept x and hence accept x if x is accepted by M.

2. If x is in A but not in B.

In this case M will not accept x(as it is not in B) and N will not accept x(as it is not in complement of A and not in B) and hence accept x if neither M nor N accept it.

3. If x is not in A but in B.

In this case M will not accept x but N will accept it(since x is in B) and hence reject x if this happens.

4. If x is not in A and not in B as well

In this case, M will reject x but N will accept it(since x is in complement of A) and hence reject x if this happens .

Since all the 4 cases, the behavior of Turing machine M and N are different when x is in A than when x is not in A and hence we will be able to decide A and hence A is decidable.

Please comment for any clarification .

.

Similar Solved Questions

1 answer
How do you simplify #12^(10/8)/12^(-3/8)#?
How do you simplify #12^(10/8)/12^(-3/8)#?...
1 answer
3 pts Question 4 Sandra is a client of yours whom completed a 3-day diet record....
3 pts Question 4 Sandra is a client of yours whom completed a 3-day diet record. Based on your analysis, she consumes an average of 75 grams of protein, 250 grams of carbohydrates, and 45 grams of fat per day. How many kcalories total does she consume on average per day? 20 What percent of her diet ...
1 answer
**S6.23' The school board is trying to evaluate a new math program introduced to second-graders in...
**S6.23' The school board is trying to evaluate a new math program introduced to second-graders in five elementary schools across the county this year. A sample of the student scores on standardized math tests in each elementary school yielded the fol- lowing data: SCHOOL NO, OF TEST ERRORS 35 5...
1 answer
Question 2 and 3 () Describe analog and digital signals in terms of Noise and interference...
question 2 and 3 () Describe analog and digital signals in terms of Noise and interference tolerance 2 Marks Eachl Bandwidth m) Power consumption (iv) Impedance (b) Sute real life examples of stochastic and deterministic [3 Marks (c) Differentiate between impulse response and frequency response of a...
1 answer
A particular airplane will reach liftoff at a speed of 120 km/h. (a) What minimum constant...
A particular airplane will reach liftoff at a speed of 120 km/h. (a) What minimum constant acceleration does the airplane require for it to liftoff after a takeoff run of 220 m? (Enter the magnitude only.) m/s2 (b) How long does it take the airplane to reach liftoff speed? S...
1 answer
State whether T20 underestimates or overestimates the integral 2 5e-x/4 dx T20 underestimates the integral. T20...
State whether T20 underestimates or overestimates the integral 2 5e-x/4 dx T20 underestimates the integral. T20 overestimates the integral. Find a bound for the error (but do not calculate T20). (Round your answer to five decimal places.) Error(T20) State whether T20 underestimates or overestimates...
1 answer
5. [-12 Points] DETAILS LARCALCET7 2.2.033.MI. Consider the following. <<2 2 <<4 8 - 2x 6....
5. [-12 Points] DETAILS LARCALCET7 2.2.033.MI. Consider the following. <<2 2 <<4 8 - 2x 6. Sketch the graph of f. 6 2 2 2 4 8 0 10 -10 -6 4 -2 2 -6 y 2 R 2 4 10 -10 0 -6 -2 2 -2 Identify the values of c for which the following limit exists. lim f(x) The limit exists at all points on the ...
1 answer
(4) A researcher estimated a demand function for commodity "A" using weekly data collected over a...
(4) A researcher estimated a demand function for commodity "A" using weekly data collected over a 30-month period. The estimated model is presented below. Qd. 200 - 2Pa + 4.51 + 3.0 Py. where Pa = Price of commodity "A" I = Consumer incomes Py = Price of commodity Y (a)On aggregate, ...
1 answer
4. Compulsory labor refers to situations in which persons are coerced to work through the use...
4. Compulsory labor refers to situations in which persons are coerced to work through the use of violence or intimidation, or by more subtle means such as manipulation debt. How can businesses eliminate all forms of forced and compulsory labor?...
1 answer
Music Class QUESTION 18 Bata drums Oa really do speak O b.can be heard "talking" in...
Music Class QUESTION 18 Bata drums Oa really do speak O b.can be heard "talking" in Nigeria Oc. can send prayers and make jokes Od.speak the Yoruba language D e. all of the above Of. some of the above QUESTION 19 Modern researchers who believe the sun can sing are following in the tradi...
1 answer
5. In a linear collider, two particles travel toward each other from opposite directions before colliding....
5. In a linear collider, two particles travel toward each other from opposite directions before colliding. I, in the lab reference frame, an electron travels toward the collision point at 2/3 co and a positron travels at 3/4。, at what speed does the electron travel toward the positron in the ...
1 answer
Score: 12%, 1 2 of 10 pts 6.2.10-T (a) through (d) Round to four decimal places...
Score: 12%, 1 2 of 10 pts 6.2.10-T (a) through (d) Round to four decimal places as needed.) The probability that a student scored between 69 and 102 is 8375 (Round to four decimal places as needed)...
1 answer
Concept: Assessment Concept Based Case Based Experience Must be your own work in your own words...
Concept: Assessment Concept Based Case Based Experience Must be your own work in your own words Assessment #2 CB: Respiratory Scenario Purpose To provide students with the opportunity to assess a patient who is experiencing postoperative respiratory distress. Overview Marc Kozlov i...
1 answer
Homework 6 1 of 14 roblem 10.1 -Enhanced - with Feedbac 1 of 14 > Submit...
Homework 6 1 of 14 roblem 10.1 -Enhanced - with Feedbac 1 of 14 > Submit Request Answer nstant ble Pa rt B A 1.3 kg book is lying on a 0.75 m -high table. You pick it up and place it on a bookshelf 2.2 m above the floor During this process, how much work does your hand do on the book? Express you...
1 answer
1. One way that gene expression is regulated is in the remodeling of chromatin. Describe the...
1. One way that gene expression is regulated is in the remodeling of chromatin. Describe the three mechanisms of changes in the structure of the nucleosome as well as the effect of acetylation and methylation on gene expression? 2. Describe the impact of deletion, duplication, inversion and translo...
1 answer
(> Options v No results Question 30 A 60-year-old patient with diabetes is ordered paclitaxel and...
(> Options v No results Question 30 A 60-year-old patient with diabetes is ordered paclitaxel and cisplatin. The nurse assesses the patient's increased risk for: peripheral neuropathy. pulmonary thromboembolism myocardial infarction. hypersensitivity reaction. Question 31 One example of a bio...
1 answer
Apple made headlines by announcing that the price for its new iPhone X (a fancy term...
Apple made headlines by announcing that the price for its new iPhone X (a fancy term for 10) will range from $999 to $1,149. These prices are commanding attention because they are significantly higher than the base prices of the two other iPhone models that were also announced, the 8 ($699) and the ...