Homework Answers
Let the input tape be int the form 00....000w(x)0w(y)000...00
The transition graph of the given turing machine is as follows:-
Here for all the values of x we insert 3 Z at the end of the string, then after inserting all Z we subtract y number of Z from the tape, and at last we convert all the Z into 1, which will be the final output string.
To check the turing machine let us take an input string w(x) =111 and w(y) = 11, the transition table for the given string is as follows:-
| Present state | Input symbol | Change to | Next state | Move |
|---|---|---|---|---|
| q0 | 1 | X | q1 | R |
| q1 | 1 | 1 | q1 | R |
| q1 | 1 | 1 | q1 | R |
| q1 | 0 | 0 | q2 | R |
| q2 | 1 | 1 | q2 | R |
| q2 | 1 | 1 | q2 | R |
| q2 | 0 | Z | q3 | R |
| q3 | 0 | Z | q4 | R |
| q4 | 0 | Z | q5 | L |
| q5 | Z | Z | q5 | L |
| q5 | Z | Z | q5 | L |
| q5 | 1 | 1 | q5 | L |
| q5 | 1 | 1 | q5 | L |
| q5 | 0 | 0 | q6 | L |
| q6 | 1 | 1 | q6 | L |
| q6 | 1 | 1 | q6 | L |
| q6 | X | X | q0 | R |
| q0 | 1 | X | q1 | R |
| q1 | 1 | 1 | q1 | R |
| q1 | 0 | 0 | q2 | R |
| q2 | 1 | 1 | q2 | R |
| q2 | 1 | 1 | q2 | R |
| q2 | Z | Z | q2 | R |
| q2 | Z | Z | q2 | R |
| q2 | Z | Z | q2 | R |
| q2 | 0 | Z | q3 | R |
| q3 | 0 | Z | q4 | R |
| q4 | 0 | Z | q5 | L |
| q5 | Z | Z | q5 | L |
| q5 | Z | Z | q5 | L |
| q5 | Z | Z | q5 | L |
| q5 | Z | Z | q5 | L |
| q5 | Z | Z | q5 | L |
| q5 | 1 | 1 | q5 | L |
| q5 | 1 | 1 | q5 | L |
| q5 | 0 | 0 | q6 | L |
| q6 | 1 | 1 | q6 | L |
| q6 | X | X | q0 | R |
| q0 | 1 | X | q1 | R |
| q1 | 0 | 0 | q2 | R |
| q2 | 1 | 1 | q2 | R |
| q2 | 1 | 1 | q2 | R |
| q2 | Z | Z | q2 | R |
| q2 | Z | Z | q2 | R |
| q2 | Z | Z | q2 | R |
| q2 | Z | Z | q2 | R |
| q2 | Z | Z | q2 | R |
| q2 | Z | Z | q2 | R |
| q2 | 0 | Z | q3 | R |
| q3 | 0 | Z | q4 | R |
| q4 | 0 | Z | q5 | L |
| q5 | Z | Z | q5 | L |
| q5 | Z | Z | q5 | L |
| q5 | Z | Z | q5 | L |
| q5 | Z | Z | q5 | L |
| q5 | Z | Z | q5 | L |
| q5 | Z | Z | q5 | L |
| q5 | Z | Z | q5 | L |
| q5 | Z | Z | q5 | L |
| q5 | Z | Z | q5 | L |
| q5 | 1 | 1 | q5 | L |
| q5 | 1 | 1 | q5 | L |
| q5 | 0 | 0 | q6 | L |
| q6 | X | X | q0 | R |
| q0 | 0 | 0 | q7 | R |
| q7 | 1 | Y | q8 | R |
| q8 | 1 | 1 | q8 | R |
| q8 | Z | Z | q8 | R |
| q8 | Z | Z | q8 | R |
| q8 | Z | Z | q8 | R |
| q8 | Z | Z | q8 | R |
| q8 | Z | Z | q8 | R |
| q8 | Z | Z | q8 | R |
| q8 | Z | Z | q8 | R |
| q8 | Z | Z | q8 | R |
| q8 | Z | Z | q8 | R |
| q8 | 0 | 0 | q9 | L |
| q9 | Z | 0 | q10 | L |
| q10 | Z | Z | q10 | L |
| q10 | Z | Z | q10 | L |
| q10 | Z | Z | q10 | L |
| q10 | Z | Z | q10 | L |
| q10 | Z | Z | q10 | L |
| q10 | Z | Z | q10 | L |
| q10 | Z | Z | q10 | L |
| q10 | Z | Z | q10 | L |
| q10 | 1 | 1 | q10 | L |
| q10 | Y | Y | q7 | R |
| q7 | 1 | Y | q8 | R |
| q8 | Z | Z | q8 | R |
| q8 | Z | Z | q8 | R |
| q8 | Z | Z | q8 | R |
| q8 | Z | Z | q8 | R |
| q8 | Z | Z | q8 | R |
| q8 | Z | Z | q8 | R |
| q8 | Z | Z | q8 | R |
| q8 | Z | Z | q8 | R |
| q8 | 0 | 0 | q9 | L |
| q9 | Z | 0 | q10 | L |
| q10 | Z | Z | q10 | L |
| q10 | Z | Z | q10 | L |
| q10 | Z | Z | q10 | L |
| q10 | Z | Z | q10 | L |
| q10 | Z | Z | q10 | L |
| q10 | Z | Z | q10 | L |
| q10 | Z | Z | q10 | L |
| q10 | Z | Z | q10 | L |
| q10 | Y | Y | q7 | R |
| q7 | Z | 1 | q11 | R |
| q11 | Z | 1 | q11 | R |
| q11 | Z | 1 | q11 | R |
| q11 | Z | 1 | q11 | R |
| q11 | Z | 1 | q11 | R |
| q11 | Z | 1 | q11 | R |
| q11 | Z | 1 | q11 | R |
| q11 | 0 | 0 | qf | R |
Since the machine reaches to state qf therefore machine will stop, the final status of input tape will be in the form 0XXX0YY111111100, where the output is 1111111, which is correct
1(1,1,R) (2,2,R) (1+X,R) (0,0,R) lavo Qu2 Ov3 (0,2,R) Co,O,R) (0, 2, RY 4 (W7 (1,Y, R) K (X,X,R) (0, 2,6)' (2, 1, R) ave aus (1,1,L) (2,2,2) (2,2,R) ai (0,0,6) (0,0,L) qua (2,0,4) (2, 1, R) (Y,Y, R) Coll) (0,0,R) D (2,2,1) af) (1,1,L)
1(1,1,R) (2,2,R) (1+X,R) (0,0,R) Qu2 lavo Ov3 (0,2,R) Co,O,R) (0, 2, RY 4 (W7 (1,Y, R) K (X,X,R) (0, 2,6)' (2, 1, R) ave aus (1,1,L) (2,2,2) (2,2,R) ai (0,0,6) (0,0,L) qua (2,0,4) (2, 1, R) (Y,Y, R) Coll) (0,0,R) D (2,2,1) af) (1,1,L)
Add Answer to:
Question 2 10 pts Let x and y be positive integers (x, y > 0) represented...
Let x and y be positive integers, x > 0, y > 0, represented in unary....
Let x and y be positive integers, x > 0, y > 0, represented in unary. Assume that x < y. Design a Turing Machine that computes the function: f(x, y) = y - x. More specifically, q0w(x)0w(y) | * qf w(y-x)0 Draw the transition graph of the TM. Make sure you clearly indicate initial/final states. Do not draw the block diagram! Here is an example: x = 2, y = 5 q-0 11011111| * qf 1110 Upload a file...
02. Design Turing machine to compute the following function for x positive integers represented i...
02. Design Turing machine to compute the following function for x positive integers represented in unary. f (x) x mod 4.
02. Design Turing machine to compute the following function for x positive integers represented in unary. f (x) x mod 4.
3. Let x be a positive integer represented in unary form. Construct a Turing machine to compute t...
theory of computing
3. Let x be a positive integer represented in unary form. Construct a Turing machine to compute the function fx)-3x (replace the input by function value in unary form (e.g. qo 11 1) Design a grammar for L-(a b cho,n>o).
3. Let x be a positive integer represented in unary form. Construct a Turing machine to compute the function fx)-3x (replace the input by function value in unary form (e.g. qo 11 1) Design a grammar for...
Find all integers x, y, 0 < x, y < n, that satisfy each of the...
Find all integers x, y, 0 < x, y < n, that satisfy each of the following pairs of congruences. If no solutions exist, explain why. (a) x + 5y = 3(mod n), and 4x + y = 1(mod n), for n = 8. (b) 7x + 2y = 3(mod n), and 9x + 4y = 6(mod n), for n=5.
Let X and Y be random variables with joint density function f(x,y) бу 0 0 <...
Let X and Y be random variables with joint density function f(x,y) бу 0 0 < y < x < 1 otherwise The marginal density of Y is fy(y) = 3y (1 – y), for 0 < y < 1. True False
1. Solve the following DE: (50 pts) (1, if 0<x51 a) y+ y = f(x), y(0)...
1. Solve the following DE: (50 pts) (1, if 0<x51 a) y+ y = f(x), y(0) = 3 where f(x)= 0, if x>1 (10 pts)
Let X be a random variable with pdf S 4x3 0 < x <1 Let Y...
Let X be a random variable with pdf S 4x3 0 < x <1 Let Y 0 otherwise f(x) = {41 = = (x + 1)2 (a) Find the CDF of X (b) Find the pdf of Y.
8. (10 pts.) The moment generating functions of X and Y are given by Mx(e) =...
8. (10 pts.) The moment generating functions of X and Y are given by Mx(e) = (3x + 3) * and My (0) = + bene + cena respectively. Assuming that X and Y are independent, find (a) P{XY = 0} (b) P{XY >0} (c) Var (3X - 6Y + 2). (d) EXY.
(6 pts) Consider the joint density function f(x, y) = { (9- 2- y), 0<r<3, 3...
(6 pts) Consider the joint density function f(x, y) = { (9- 2- y), 0<r<3, 3 Sy <6, 0, otherwise Find P(0 < < <1,4 <y<6).
Let f(x,y) = 12e-2(x+y), x > 0, y > 0. Show that X, Y are independent....
Let f(x,y) = 12e-2(x+y), x > 0, y > 0. Show that X, Y are independent. What are the marginal PDFs of each?
Let x and y be positive integers, x > 0, y > 0, represented in unary. Assume that x < y. Design a Turing Machine that computes the function: f(x, y) = y - x. More specifically, q0w(x)0w(y) | * qf w(y-x)0 Draw the transition graph of the TM. Make sure you clearly indicate initial/final states. Do not draw the block diagram! Here is an example: x = 2, y = 5 q-0 11011111| * qf 1110 Upload a file...
02. Design Turing machine to compute the following function for x positive integers represented in unary. f (x) x mod 4.
02. Design Turing machine to compute the following function for x positive integers represented in unary. f (x) x mod 4.
theory of computing
3. Let x be a positive integer represented in unary form. Construct a Turing machine to compute the function fx)-3x (replace the input by function value in unary form (e.g. qo 11 1) Design a grammar for L-(a b cho,n>o).
3. Let x be a positive integer represented in unary form. Construct a Turing machine to compute the function fx)-3x (replace the input by function value in unary form (e.g. qo 11 1) Design a grammar for...
Find all integers x, y, 0 < x, y < n, that satisfy each of the following pairs of congruences. If no solutions exist, explain why. (a) x + 5y = 3(mod n), and 4x + y = 1(mod n), for n = 8. (b) 7x + 2y = 3(mod n), and 9x + 4y = 6(mod n), for n=5.
Let X and Y be random variables with joint density function f(x,y) бу 0 0 < y < x < 1 otherwise The marginal density of Y is fy(y) = 3y (1 – y), for 0 < y < 1. True False
1. Solve the following DE: (50 pts) (1, if 0<x51 a) y+ y = f(x), y(0) = 3 where f(x)= 0, if x>1 (10 pts)
Let X be a random variable with pdf S 4x3 0 < x <1 Let Y 0 otherwise f(x) = {41 = = (x + 1)2 (a) Find the CDF of X (b) Find the pdf of Y.
8. (10 pts.) The moment generating functions of X and Y are given by Mx(e) = (3x + 3) * and My (0) = + bene + cena respectively. Assuming that X and Y are independent, find (a) P{XY = 0} (b) P{XY >0} (c) Var (3X - 6Y + 2). (d) EXY.
(6 pts) Consider the joint density function f(x, y) = { (9- 2- y), 0<r<3, 3 Sy <6, 0, otherwise Find P(0 < < <1,4 <y<6).
Let f(x,y) = 12e-2(x+y), x > 0, y > 0. Show that X, Y are independent. What are the marginal PDFs of each?
Most questions answered within 3 hours.
-
You are going to sell fruits & vegetables at a local
roadside market. List separately and...
asked 38 minutes ago -
Hows does water affect the digestion of fats ?
asked 2 hours ago -
A buffer that contains 0.41 M of a base, B and 0.21 M of its
conjugate...
asked 2 hours ago -
Pleaaaaaaaasssssse help me please please it's more important
:((((((((((((((((((((
CASE STUDY
Nissan Company
Nissan Motor Company,...
asked 2 hours ago -
Calculate the concentration of hydronium and hyroxide ions in 1)
2.0 mol/L HNO3 2) 0.5 mol/L...
asked 3 hours ago -
In a loop-the-loop ride a car goes around a vertical, circular
loop at a constant speed....
asked 3 hours ago -
50 grams each of water (18.015 g/mol) and ethylene glycol
(C2H6O2) (62.07 g/mol) are mixed. At...
asked 3 hours ago -
The life expectancy of sport utility vehicles follows a normal
distribution with a mean of 145.8...
asked 3 hours ago -
If an object with mass of 5 kg is pushed with a force of 552 N,...
asked 3 hours ago -
Suppose your program already has a list called nums, which
contains several numbers. Write a for...
asked 3 hours ago -
A spherical shell with a finite thickness just barely floats in
water. If the shell is...
asked 3 hours ago -
Explain in detail whether the following is true or false:
Total factor productivity will rise only...
asked 3 hours ago