Determine what the Turing machine in Example 9.7 does when presented with the inputs aba andaaabbbb.Is there any input for which the Turing machine in Example 9.7 goes into an infinite loop? Example 9.7For E = {a,b}, design a Turing machine that acceptsL= {a,b„:n21}.Intuitively, we solve the problem in the following fashion. Starting at the leftmost a, we check it offby replacing it with some symbol, say x. We then let the read-write head travel right to find theleftmost b, which in turn is checked off by replacing it with another symbol, say y. After that, we goleft again to the leftmost a, replace it with an x, then move to the leftmost band replace it with y, andso on. Traveling back and forth this way, we match each a with a corresponding b. If after some timeno a's or b's remain, then the string must be in L.Working out the details, we arrive at a complete solution for which Q= {qo91;9293,94},F= {q4},E= {a,b},T={a,b, x, y,¤}. The transitions can be broken into several parts. The set

Solution :: Let's see first what is turing machine called :: Turing machine is mathematical model…

Answered: Determine what the Turing machine in…

Determine what the Turing machine in Example 9.7 does when presented with the inputs aba and aaabbbb. Is there any input for which the Turing machine in Example 9.7 goes into an infinite loop?

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Q: draw the state diagram of a Turing Machine that will compute x + y, where x and y are given in unary…

A: The Turing Machine is shown below. First, we put a # at the end, then we replace every left-hand 1…

Q: Let ALLpFA={(M)| M is a DFA and L(M) = £*} Determine if ALLDFA is Turing-decidable and prove your…

Q: Let T = {(M) | M is a Turing machine which, when started with a blank tape, eventu- ally enters each…

A: Given:

Q: Design a Turing machine that, when started scanning a square on a completely black tape, writes the…

A: Turning machine: It is a mathematical model used to study behaviour of computer. The turning machine…

Q: Define the notion of a Turing machine with a two-dimensional tape. Show that a 2-tape ordinary…

A: Introduction: A Turing machine consists of a tape of infinite length on which read and writes…

Q: Draw a Turing machine that accepts the language { ai bi | i != j }.

A: A Turing machine is a mathematical model of computation originally proposed by British mathematician…

Q: Construct a deterministic two-tape Turing machine, which begins with a string of the form anon the…

A: Algorithm approach- we first scan leftmost side of each tape if it is a we move right until first…

Q: Machine learning algorithms are sometimes grouped into two broad groups of lazy and eager…

A: Answer in step2

Q: In "Computing Machines and Intelligence," the English mathematician Alan Turing (1912-1954) wrote,…

A: Computing Machines and Intelligence: Computing Machines and Intelligence is the study of how to…

Q: Construct a Turing machine that computes the function f(n) = +2 for all nonnegative integers n.

A: A Turing machine is a hypothetical machine that controls images on a tape strip, in light of a table…

Q: Build a Turing Machine T.M with three tracks that add two binary numbers. We will consider that the…

A: ’10*10′ => ‘100’, ’11*10′ => ‘110’.Let’s test the turning machine with the input as ’11*1′ #…

Q: Determine and draw a matrix or a state machine of the Turing machine that computes the function:…

A: The Turing machine is a mathematical model that manipulates the abstract machine and computing…

Q: Consider A2 Turing Machine which is a variation of A Turing Machine where the pairs only include…

A: Complete step-by-step answer is below:

Q: Suppose that there is a TM which on any input does not move its head more than n squares to the…

A: Turing language: Ripley is a high-level, summary real language created by Ric Harrison and James…

Q: Consider the Turing Machine defined as follows: (q0,0,q0,0,R), (q0,1,q1,0,R), (q0,B,q2,B,R),…

A: In given Turing machin, we have define what machine will do whenever we pass any string. We have…

Q: (So, 0, S1, 0, L) (S₁, 1, S₁, 1, R) (S2, 0, S3, 1, R) state (So, 1, S1, 0, L) (So, B, S1, 1, R) (S3,…

A: For each part, Initially, we start with T in state s0 and position over the leftmost nonblank symbol…

Q: Using unary representations of numbers so that the only symbols are B and 1, write down 5- tuples…

A: Here is the explanation regarding the given Turing machine.

Q: Problem 8: Design a Turing machine that takes inputs like ...B1110111111B.... deletes the middle 0,…

A: Convert a 0 in the first number in to X and then traverse entire input and convert the first blank…

Q: LetΣ ={a, b}. LetL={aibai|i≥0}.Give a Turing machine (TM) that accepts the languageL.Assume (as in…

Q: Construct a Turing machine that recognizes the set of all bit strings that end with the sequence…

A: solution - write down 5 - tuples that will define a twing machine that acognies the set of all bit,…

Q: tate diagram for a Turing machine that starts with a but dont have bb

A: Given: Draw a state diagram for a Turing machine that starts with a but dont have bba.

Q: LetΣ ={a, b}. LetL={aibai|i≥0}.Give a Turing machine (TM) that accepts the languageL.Assume (as in…

A: The complete answer is given below.

Q: Consider L={(TM) | TM stands for the Turing machine, which halts on all input, and L(TM)= L' for…

A: Given data: Consider L={(TM) | TM stands for the Turing machine, which halts on all input, and…

Q: Using adders, subtractors, comparers, copiers or multipliers, draw a block diagram for a Turing…

A: INTRODUCTION: An adder, sometimes known as summer, is a digital circuit that performs numerical…

Q: Let x, y, z be positive integers (x, y, z> 0) represented in unary. Assume that x> z. Design a…

Q: True or False. There is a deterministic Turing machine M that will convert any NFA into an…

A: Answer to the given question: A turing machine consists of a tape of infinite length on which read…

Q: The Turing machine M below recognizes the language L= (02" | n ≥ 0}. 0/0, L 2/2.1 2/1, R A/A.R A/A.R…

A: Consider the language , consisting of all strings of whose length is a power of 2. Turing machine…

Q: Design and write out in full a turing machine that scans to the right until it finds two consecutive…

Q: Create a Turing machine for the language anbncmdm, where n,m > 0.

Q: Let T be the Turing Machine defined by the 5-tuples, (So. 0, 0, S₁, L) (So. 1, 0, S. L) (So, B, B,…

Q: Draw a Turing machine that has an input alphabet of { a, b, c }, and when it runs on an input…

A: According to the information given:- We have to draw a turing machine that has an input alphabet of…

Q: Build a turing machine with three tracks that add two binary numbers. Considerate the data is stored…

A: Turing Machine for addition A number is represented in binary format in different finite automata.…

Q: Design a Turing machine with no more than three states that accepts the language L(a(a+b)*). Assume…

A: Answer is given below-

Q: ring machine that computes the function ?(?)=2? , i.e. if the input is 0^? then the output should be…

A: The solution is an given below :

Q: 9. The Turing Machine M below accepts L = { a"b": n >= 1}. y;y,R а; а, R y:y, L а; а, L q1 b;y. L…

A: Solution ======================================================================== after tracing the…

Q: Design a Turing Machine that accepts L L= {ww | we (a, b)} Please show all the steps.

Q: reate a Turing machine for the language anbncmdm, where n,m > 0.

A: The language L = {anbmcnm | n >= 0 and m>=0} represents a kind of language where we use only 3…

Q: Question 1. Below is the transition diagram for a Turing machine. a, a, R а, а, L b, b, R b, b, L a,…

A: Solution: Given Turing machine with transition diagram as shown and we need to find which sting halt…

Q: For each iteration of a Turing machine, provide a schematic and an input string.

A: Given: Create an exact diagram for each kind of Turing machine and a description of its input…

Q: Construct a Turing machine that takes strings over the alphabet {a,b} on the tape, and moves the…

A: A Turing machine is a theoretical model of a computer that was first introduced by Alan Turing in…

Q: Given the Turing Machine M as follows. (image) Complete the following: (A) Complete the…

A: An abstract computing model known as a Turing machine does calculations by reading from and…

Q: Let A = { IM is a turing machine and IL(M) (>100}. Is A decidable (yes/no)? Prove i

A: hey student i will work on it

Q: Construct a Turing machine that will compute f(x) = 2x when x is given in unary representation.

A: The complete answer is below:

Q: Testing strings: €, 0, 1, 01, 10, 001, 011, 0011, 0101, 1010 The accepted strings are:

A: Consider the given language is L={ 0n1n | n >=1 }

Q: . Which of the following strings are accepted by the following Turing machine with q5 is the final…

A: Defined the language accepted by the given Turing machine a. L={ w ∈ ∑*| |w|=0(mod 3) over ∑={a,…

Concept explainers

Problems on Turing Machines

In the computational world, the Turing machine is a powerful computation engine. The invention of the Turing Machine is done by Alan Turing in 1936. A Turing Machine (TM) is a diagrammatic model of a fictional computer. It determines an output from a set of input variables using a pre-defined set of rules. It is used to get around the limitations of finite automata and pushdown automata.

Question

Determine what the Turing machine in Example 9.7 does when presented with the inputs aba and
aaabbbb.
Is there any input for which the Turing machine in Example 9.7 goes into an infinite loop?

Example 9.7
For E = {a,b}, design a Turing machine that accepts
L= {a,b„:n21}.
Intuitively, we solve the problem in the following fashion. Starting at the leftmost a, we check it off
by replacing it with some symbol, say x. We then let the read-write head travel right to find the
leftmost b, which in turn is checked off by replacing it with another symbol, say y. After that, we go
left again to the leftmost a, replace it with an x, then move to the leftmost band replace it with y, and
so on. Traveling back and forth this way, we match each a with a corresponding b. If after some time
no a's or b's remain, then the string must be in L.
Working out the details, we arrive at a complete solution for which Q= {qo91;9293,94},F= {q4},
E= {a,b},T={a,b, x, y,¤}. The transitions can be broken into several parts. The set

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

This is a popular solution!

SEE SOLUTION Check out a sample Q&A here

Step 1

Step 2

Step 3

Step 4

Trending now

This is a popular solution!

Step by step

Solved in 4 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions

Design a Turing machine that accepts L. L = {ww | w ԑ (a, b)+} Draw the tape and write down the instantaneous descriptions.
Draw a state diangram for a Turing machine which, when given an input string 0", outputs 0"1". For example, if the tape contains 0000 at the beginning, then the tape should contain 00001111 when the TM halts. You may omit transitions that won't ever be taken. 4.
Let M be a Turing machine and w be a string in the input alphabet of M. Consider the problem A = {(M, w)|M moves left at some point during its computation on w} %3| Show that A is decidable.
If P≠NP, can the computational decision problems that can be solved by a nondeterministic turing machine, but not by a regular Turing machine exist? Explain.
Define a Turing machine that accepts an integer n as an input string in unary representation, w = { 1 } *, and calculates n mod 3. When the machine halts, the tape should contain only the unary representation of f(w) followed by a zero. For example, ƒ(1111) = 10 or f(11111) 11111) = 0.
Construct a Turing machine that computes the function ? of ? is equal to two ?, i.e. if the input is zero to the power ? then the output would be zero to the power two ? e.g. if it says 000 on the tape before the machine is run it should read 000000 on the tape when it has stopped.
Construct a Turing machine that copies the first three nonblank symbols over the next three blank symbols.
not handwritten Prove that the following problem is not decidable: Given a Turing Machine M, does the machine reject every input. (i.e., does L(M) = ∅)?
Consider the Turing Machine defined as follows: (q0,0,q0,0,R), (q0,1,q1,0,R), (q0,B,q2,B,R), (q1,0,q1,0,R), (q1,1,q0,1,R) and (q1,B,q2,B,R). Describe what this TM does when presented with bit strings defined over the alphabet Σ = {0,1} as input. (Note: B = Blank).
(b) Suppose that you were asked to design a Turing machine that, when started scan- ning a square on a completely blank tape, writes the string ababbaab on the tape and halts scanning the leftmost symbol of this string. What is the minimal number of states required in order to accomplish this?
LetΣ ={a, b}. LetL={aibai|i≥0}.Give a Turing machine (TM) that accepts the languageL.Assume (as in the examples done in our course videos) that, when theTM starts, the head is on a blank symbol,∆, and the input string isimmediately after that blank symbol on the tape. For example, if theinput string wereaaabaaa, then the inital tape configuration would be∆aaabaaa
Computer Science You are told that state machine A has one input x, and one output y, both with type {1, 2}, and that it has states {a, b, c, d}. You are told nothing further. Do you have enough information to construct a state machine B that simulates A? If so, give such a state machine, and the simulation relation.