ZuoTi.Pro
Question

5. Design a Turing machine that takes as input two numbers a and b, such that a is not equal to b and determines which number is higher. Give the transition table for the machine. Show by drawing the steps, how the machine works when a-3 and b-2. Can we use a PDA for the same problem? Give reasons for your answer (10+5+5-20).

engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

6/5*- 7 ala← 시 xe Cah

We can use PDA. Given below is the one.

e,a/a a,z/az a,alaa b,4/e a ble

2 0
Add a comment
Know the answer?
Add Answer to:
5. Design a Turing machine that takes as input two numbers a and b, such that...
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

  • Discrete Mathematical Structures Draw a Turing machine that takes a string representing two unary numbers, x...

    Discrete Mathematical Structures Draw a Turing machine that takes a string representing two unary numbers, x and y, separated by a 0, and determines whether x greaterthanorequalto y. For example, the input for x = 3, y = 4 would be 11101111. Use two halt states: one for yes and one for no. Give the trace of your machine in the previous problem processing the strings 11101111 and 11110111. Draw a TM that computes f(w) = w^R where w elementof...

  • Problem 3: Turing Machine Models Turing-Recognisablity and Decidability [20] a. Show that an FA w...

    Subject : Theory of Computation Please answer , posting second time now cause nobody answered it previously Problem 3: Turing Machine Models Turing-Recognisablity and Decidability [20] a. Show that an FA with a FIFO queue is Turing universal (i.e equivalent in computational power to a Turing machine). You should regard this machine as being formally defined in a way that is very similar to a PDA, except that on each transition, instead of pushing and/or popping a character, the machine...

  • Question 8. Design a Turing machine that calculates the sum of two unary numbers. (You can...

    Question 8. Design a Turing machine that calculates the sum of two unary numbers. (You can assume the input consists of two unary numbers separated by a single blank space.)

  • . Please design a standard TM (i.e., a single semi-infinite tape, deterministic) for the laın gua...

    . Please design a standard TM (i.e., a single semi-infinite tape, deterministic) for the laın guage of all palindromes over alphabet {a, b} . Please give both the high-level description (text description or pseudo-code algorithm) and the low-level state transition diagram. Please analyze how many steps (one transition is considered as a step) it takes to accept an input palindrome with n symbols . Please design a deterministic Turing machine with two semi-infinite tapes for the same language. Please give...

  • Write a TM (Turing Machine) program that adds two base two numbers. Input is two nonnegative inte...

    Write a TM (Turing Machine) program that adds two base two numbers. Input is two nonnegative integers in base 2 with a plus sign between them. Output is their sum in base 2, with nothing else left on the tape. So first decrement, then increment. Use an online Turing Machine Simulator to see how it works. Use the following language for the program: current state, read symbol, next state, write symbol, direction [directions are (< left, > right, s stay)]...

  • turing machine transition table Use the input and table to execute. Input: babaaa b a (q2,...

    turing machine transition table Use the input and table to execute. Input: babaaa b a (q2, b, R) (q1, b, R) (q0, a, L) qo (q3, *, L) (q1,* L) (q2, a, L) 97 (q2, b, R) (q1,* R) (q0, a, R) q2 (q3, *, R) (q1, b, R) (q0, a, R) q3 First 6 characters of the tape after step 1: Ex: *abb*b Select the state of the Turing Machine after each step: Step 1 Use the input and...

  • Design a digital circuit that takes two 4-bit numbers A and B as input and generates...

    Design a digital circuit that takes two 4-bit numbers A and B as input and generates output Z as follows: (20 points) - If A and B are odd numbers then Z-A-B. - If A and B are even numbers then Z-B-A 5. If A is an even number and B is an odd number then Z-A+B If A is an odd number and B is an even number then Z-A-B-1 Assume that you have access to as many as...

  • Many of you asked why we couldn't have two stacks for PDAs? Now here comes a...

    Many of you asked why we couldn't have two stacks for PDAs? Now here comes a problem for you. It is natural to add an extra stack to a PDA Say M is a two-stack PDA if M is exactly the same as a PDA but with two stacks. Each instruction (transition) in M is in the form of which means that if M is at state q and reading input symbol a with the M to state p, and...

  • a) What language is accepted by the Turing machine d(%-a)-(%-a, R), d(%-a)-(9-a, R). (5) Design a...

    a) What language is accepted by the Turing machine d(%-a)-(%-a, R), d(%-a)-(9-a, R). (5) Design a Turing machine that will accept language OL-L6.a) (6) Design a Turing machine that will calculate fx)-3x. You must show the representation of s and 3x on the tape of Turing machine when the calculation starts and ends, respectively Extra Questions (20 points) 1. Fill the proper words in the blank (1) Given alphabet Σ, a language on Σ isa (2) Given a grammar G,...

  • Answer and explain your answer QUESTION 5 A Turing machine M with start state go and...

    Answer and explain your answer QUESTION 5 A Turing machine M with start state go and accepting state of has the following transition function: 1 8(q,a) 0 B 40 (90,1,R) (91,1,R) (9f,B,R) 91 (42,0,L) (42,1,L) (92,B,L) 42 (90,0,R) 9f Deduce what M does on any input of O's and I's. Hint: consider what happens when M is started in state qo at the left end of a sequence of any number of 0's (including zero of them) and a 1....

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