ZuoTi.Pro
Question

3. (20) Give proofs of the following: a. The question: Given a DFA M and a string w, does M accept w is decidable. b. Given two Turing-acceptable language Li and L2, the language LtLz is also Turing-acceptable. [D not use non-determinism. Do be sure to deal with cases where a TM might loop.l
engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

a) Decidable means we should have an algorithm to find the solution to
   a problem.So in this case we have a method to find out whether a DFA
   accepts a string w or not. If after processing w it reaches an accepting state means it is excepted by M otherwise not. So this problem is decidable


b) L1 is Turing acceptable and L2 is turing acceptable then l1l2 is also
   Turing acceptable because we can create a turing machine by placing
   two turing machines T1 and T2 in parallel and identify whether a string
   is acceptable or not by individually looking at the acceptable state
   of individual machines.

0 0
Add a comment
Know the answer?
Add Answer to:
3. (20) Give proofs of the following: a. The question: "Given a DFA M and a...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • Please also note that there might be multiple answers for each question. Q1: Which of the following claims are true?*...

    Please also note that there might be multiple answers for each question. Q1: Which of the following claims are true?* 1 point The recognizable languages are closed under union and intersection The decidable languages are closed under union and intersection The class of undecidable languages contains the class of recognizable languages For every language A, at least one of A or A*c is recognizable Other: This is a required question Q2: Which of the following languages are recognizable? (Select all...

  • Show that the language A = {<M1> | the language accepted by the Turing Machine M1...

    Show that the language A = {<M1> | the language accepted by the Turing Machine M1 is 1*} is not decidable. Present your proof in the style of the proof of Th. 5.3, which shows below. PROOF We let R be a TM that decides REGULARTm and construct TM S to decide ATM. Then S works in the following manner. S - "On input (M, w), where M is a TM and w is a string: 1. Construct the following...

  • Determining whether languages are finite, regular, context free, or recursive 1. (Each part is worth 2 points) Fill in the blanks with one of the following (some choices might not be used): a) finit...

    Determining whether languages are finite, regular, context free, or recursive 1. (Each part is worth 2 points) Fill in the blanks with one of the following (some choices might not be used): a) finite b) regular but not finite d) context-free but not deterministic context-free e) recursive (that is, decidable) but not context-free f) recursively enumerable (that is, partially decidable) but not recursive g) not recursively enumerable Recall that if M is a Turing machine then "M" (also written as...

  • Question 1: Design a DFA with at most 5 states for the language L1 = {w...

    Question 1: Design a DFA with at most 5 states for the language L1 = {w ∈ {0, 1}∗ | w contains at most one 1 and |w| is odd}. Provide a state diagram for your DFA. Approaching the Solution --since we haven’t really practiced this type of assignment (i.e. had to define our machine based on only having the language given; not the formal 5 tuples), I am providing the steps for how to work through this; you are...

  • 3. [20 points] Give short answers to each of the following parts. Each answer should be...

    3. [20 points] Give short answers to each of the following parts. Each answer should be at most three sentences. Be sure to define any notation that you use. (a) Explain the difference between a DFA and an NFA. (b) Give a regular expression for the language consisting of strings over the alphabet 2-(0, 1) that contains an even number of 0's and an odd number of 1's and does not contain the substring 01. (c) Give the formal definition...

  • 19. (1 point) Suppose that L is undecidable and L is recognizable. Which of the following...

    19. (1 point) Suppose that L is undecidable and L is recognizable. Which of the following could be false? A. I is co-Turing recognizable. B. I is not recognizable. C. I is undecidable. D. L* is not recognizable. E. None of the above. 20. (2 points) Let ETM {(M)|L(M) = 0} and EQTM = {(M1, M2)|L(Mi) = L(M2)}. We want to show that EQTM is undecidable by reducing Etm to EQTM and we do this by assuming R is a...

  • 3.(4 4+20-36 points Formal Definition of a Turing Machine (TM) ATM M is expressed as a...

    3.(4 4+20-36 points Formal Definition of a Turing Machine (TM) ATM M is expressed as a 7-tuple (Q, T, B, ? ?, q0,B,F) where: . Q is a finite set of states T is the tape alphabet (symbols which can be written on Tape) .B is blank symbol (every cell is filled with B except input alphabet initially .2 is the input alphabet (symbols which are part of input alphabet) is a transition function which maps QxTQxTx (L, R :...

  • Question 3: (45 marks] Suppose the price-setting equation is given by P= (1 + m)W where...

    Question 3: (45 marks] Suppose the price-setting equation is given by P= (1 + m)W where m is the markup. The wage-setting equation is given by W = pe? where z are unemployment benefts and u is the unemployment rate. 1. Derive the real wage and unemployment consistent with equilibrium in the labor market in the medium run. Is this the natural rate of unemployment? Does the equilibrium rate of unemployment change if unemployment benefts decrease? Explain? (8 marks] 2....

  • Question 3: (45 marks] Suppose the price-setting equation is given by P= (1+mW where m is...

    Question 3: (45 marks] Suppose the price-setting equation is given by P= (1+mW where m is the markup. The wage-setting equation is given by W = pe? where z are unemployment benefts and u is the unemployment rate. 1. Derive the real wage and unemployment consistent with equilibrium in the labor market in the medium run. Is this the natural rate of unemployment? Does the equilibrium rate of unemployment change if unemployment benefts decrease? Explain? (8 marks] 2. Draw the...

  • Write the following functions, as defined by the given IPO comments. Remember to include the IPO...

    Write the following functions, as defined by the given IPO comments. Remember to include the IPO comments in your submission. Be sure to test your code -- you can use the examples given for each function, but you should probably test additional examples as well -- and then comment-out or remove your testing code from your submission!. We will be testing your functions using a separate program, and if your own testing code runs when we load your file it...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT