Assignment 6: Problem Set on TMs.1. Given the following definition of a Turing machine M = (Q, E, I, 6, 91, accept, Greject):• Q={91, 92,98, Jaccept, greject}« Σ = {0, 1, #}• T = EU {z, u}0-0, R1-1,R## .R0-2,R90-2, L9:970-0, L1-1, L#-#.R1-2, R9s3. Prove that every regular language is decidable.##.R91-3, L0-0, R1-1, R0-0, L1-1,4z-z, RSimulate the Turing machine on input (a) 010#1 and (b) 1#1.Use the concept of configurations to illustrate the transitions.z-z.RGarapeNote: To simplify the figure, the reject state and transitions going to the reject state are not shown.Those transitions occur implicitly whenever a state lacks an outgoing transition for a particularsymbol.R2. Let A be the set of all strings over the alphabet (a, b) where the number of a's is twice as muchas the number of b's. Construct the state diagram of a Turing machine that recognizes A.

A Turing machine which refers to an abstract computational model which are that used to performs…

1. Given the following definition of a Turing machine M = (Q, E, I, 6, 9₁, 9accept, Greject): Q-91-9298- Jaccept-greject} Σ= {0, 1, #} • I = EU {z, u} . 8: 0-0, R 1-1,R 2-2, R 0-2,R 9 R z-2, R #-#.L 1-z,R 0-0,4 1-1,L 1-2, L 0-0, L 1-1,4 2-2, L 0-0, R 1-1,R #.R z-z.R Simulate the Turing machine on input (a) 010#1 and (b) 1# 1. Use the concept of configurations to illustrate the transitions. Garape Note: To simplify the figure, the reject state and transitions going to the reject state are not shown. Those transitions occur implicitly whenever a state lacks an outgoing transition for a particular symbol.

1. Given the following definition of a Turing machine M = (Q, E, I, 6, 9₁, 9accept, Greject): Q-91-9298- Jaccept-greject} Σ= {0, 1, #} • I = EU {z, u} . 8: 0-0, R 1-1,R 2-2, R 0-2,R 9 R z-2, R #-#.L 1-z,R 0-0,4 1-1,L 1-2, L 0-0, L 1-1,4 2-2, L 0-0, R 1-1,R #.R z-z.R Simulate the Turing machine on input (a) 010#1 and (b) 1# 1. Use the concept of configurations to illustrate the transitions. Garape Note: To simplify the figure, the reject state and transitions going to the reject state are not shown. Those transitions occur implicitly whenever a state lacks an outgoing transition for a particular symbol.

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

Similar questions

1. Which of the following strings are accepted by the following Turing machine with q5 is the final state? aab, abb, aaabb, aaab, aaaaabbb δ (q0; a) = (q1; a; R); δ (q1; a) = (q2; a; R); δ (q2; a) = (q3; a; R); δ (q3; a) = (q3; a; R); δ (q3; b) = (q4; b; R); δ (q3; blank) = (q5; blank; L); δ (q4; b) = (q4; b; R); δ (q4; blank) = (q5; blank; L); 2. What language is accepted by the Turing machine in Q1?
Consider the following language L over Σ = {0, 1, 2}: L = { 0i2 1 2 02i1i | i ≥ 0 } 1. Construct a Turing machine accepting L. Justify your answer, explaining how the TM youconstructed will accept words in the language L. 2. Give an accepting run of your TM for the word 0212001 Hint: think about the TM accepting the language { 0i2 1 2 02i1i | i ≥ 0 } and how can it be changed to accept the language above. Notation: recall that e.g. we write 0i for the word consisting of i-many 0’s.
Design a Turing machine M that decides the language L = {0n1n|n> 0}.
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.
Construct a Turing Machine that recognizes all palindromes of even lengthover the alphabet {a, b}, i.e. L = {wwR |w ∈{a, b}∗and wR is the reverse of w}
Question 2. Let >= {1}. Design a Turing Machine M that adds a copy of the input string w to the tape resulting in ww. That means starting from the initial configuration qow, the machine terminates at a final state once the tape contains the string ww. For example, assuming that the tape's content is initially 111b (where b indicates the blank is a non-alphabet tape symbol at the end of the string 111, the machine terminates in an accept state with the tape content being 111111b. We say the machine outputs 111111.
Imagine a Turing machine M' that works like a normal Turing machine except that whenever it moves to the left, it moves by two squares instead of one. Its movements to the right are by one square as usual. Show that M' can compute all functions that normal Turing machines can compute.
Suppose that Turing machine M computes the unary number-theoretic function f defined by f(n) = n2 + 6n + 3 and suppose, further, that M is started scanning the leftmost 1 in an unbroken string of six 1s on an otherwise blank tape. Then M will halt scanning the leftmost 1 in an unbroken string of how many 1s?
1. Determine the Turing machine that computes the function: f(n) = 4n+3 The machine should therefore start with a natural number n on the tape and stop with the number 4n+3 on it the tape . (Hint: Think binary.) 2. Determine a Turing machine for creating palindromes. That is, if we start with w on the tape, then we should end with ww on the tape, where w is the reversed string of w. E.g. if we start with |-011 on the tape, then we should stop with |-011110 on the tape
What is the language accepted by the following Turing machine N? 9⁰ B, B, R qf a, a, R b, b, R a, a, R b, b, R Answer Choices: a. L = {w€ Σ* ||w|= 0(mod 3)} over Σ = {a,b} b. L = {w€ Σ* ||w|= 0(mod 2)} over Σ = {a,b} c. L = {w€ Σ* ||w| = odd} over Σ = {a,b} d. L = {w€ Σ* ||w| = |w\,} over Σ = {a,b} a q1 92 a, a, R b, b, R
A 2-dimensional Turing machine has an infinite 2-dimensional grid asits storage device (one cell for every address (i, j) ∈Z×Z). Instead ofL and R, there are 5 options for the head to move from (i, j): Left (to(i −1, j), Right (to (i + 1, j)), Up (to (i, j + 1)), Down (to (i, j −1)),and Stay (remain at (i, j)) .Let us assume, that our 2-dimensional TM M has an additional 1-dimensional tape where the input is located as in a 1-tape TM. The2-dimensional storage device contains a blank symbol in every cell atthe start of the computation.Show that a 2-dimensional TM is not more powerful, i.e., every lan-guage accepted by a 2-dimensional TM M is accepted by one of ourstandard 1-dimensional TMs. You don’t have to simulate directly witha 1-tape TM, as you are allowed to use what we know about k-tape(1-dimensional) TMs without proof.Describe the moves of a simulating TM M ′ in plain English. For everypossible move of M , you have to design a sequence of moves of M ′that simulates that move of…
Suppose a genetic algorithm uses chromosomes of the form x = abcdefghwith a fixed length of eight genes. Each gene can be any digit between 0 and 9. Let the fitness of individual x be calculated as: ?(?)=(?+?)−(?+?)−(?+?)−(?+ℎ) And let the population consist of fiveindividuals with the following chromosomes: ?1=12345678 ?2=23456781 ?3=45637281 ?4=53617284 ?5=23921285 a)Computethe fitness value for each individual and sort them in order with the fittest first and the least fit last. b)To create mating pool, roulette wheel selection is used. You will select the individuals. The random values to perform roulette wheel selection are 0.15, 0.56, 0.50, 0.68, and 0.95respectively. Please construct the mating pool step by step and write the selected individuals clearly. c)Perform thefollowing crossover operations in the mating pool: i)Cross the fittest two individuals using one–point crossover at the middle point. ii)Cross the second and third fittest individuals using a two–point crossover…