The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged turingmachine
Turing Machine Notes
0
votes
0
answers
1
Ullman (TOC) Edition 3 Exercise 8.2 Question 2 (Page No. 335  336)
Design Turing machines for the following languages$:$ $\text{The set of strings with an equal number of 0's and 1's.}$ $\{a^{n}b^{n}c^{n}n\geq 1\}.$ $\{ww^{R}\text{w is any string of 0's and 1's\}}.$
asked
Apr 13, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

28
views
ullman
theoryofcomputation
turingmachine
0
votes
2
answers
2
Made Easy Test Series : TOC Turing Machine
Consider $\left \langle M \right \rangle$ be the encoding of a turing machine as a string over alphabet $\Sigma =\left \{ 0,1 \right \}$. Consider $D=${$\left \langle M \right \rangle$ $M$ is TM that halt on all ... NonRecursive $(C)$ Recursively enumerable $(D)$ Not Recursively enumerable My question is Is it not a Halting Problem they are asking for?
asked
Apr 13, 2019
in
Theory of Computation
by
srestha

567
views
theoryofcomputation
turingmachine
testseries
0
votes
0
answers
3
Ullman (TOC) Edition 3 Exercise 8.2 Question 1 (Page No. 335)
Show the $ID's$ of the Turing machine of Fig.$8.9$ if the input tape contains$:$ $00$ $000111$ $00111$
asked
Apr 13, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

47
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
4
Ullman (TOC) Edition 3 Exercise 8.1 Question 1 (Page No. 324)
Give reductions from the helloworld problem to each of the problems below. Use the informal style of this section for describing plausible program transformations, and do not worry about the real limits such as maximum file size or ... $?$
asked
Apr 12, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

32
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
5
Peter Linz Edition 5 Exercise 9.3 Question 1 (Page No. 248)
Consider the set of machine language instructions for a computer of your choice. Sketch how the various instructions in this set could be carried out by a Turing machine.
asked
Apr 9, 2019
in
Theory of Computation
by
Rishi yadav

25
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
difficult
0
votes
0
answers
6
Peter Linz Edition 5 Exercise 9.2 Question 8,9,10 (Page No. 245)
$\text{Exercise 8}:$ Give an implementation of the macroinstruction $\text{searchright} (a,q_i,q_j),$ ... $a$ by a blank. If the input contains no $a$, replace the rightmost nonblank symbol by a $b.$
asked
Apr 9, 2019
in
Theory of Computation
by
Rishi yadav

14
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
7
Peter Linz Edition 5 Exercise 9.2 Question 7 (Page No. 245)
Sketch the construction of a Turing machine that can perform the addition and multiplication of positive integers $x$ and $y$ given in the usual decimal notation.
asked
Apr 9, 2019
in
Theory of Computation
by
Rishi yadav

27
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
8
Peter Linz Edition 5 Exercise 9.2 Question 6 (Page No. 245)
Suggest a method for representing rational numbers on a Turing machine, then sketch a method for adding and subtracting such numbers.
asked
Apr 9, 2019
in
Theory of Computation
by
Rishi yadav

40
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
9
Peter Linz Edition 5 Exercise 9.2 Question 5(e) (Page No. 245)
Provide a “highlevel” description for Turing machines that accept the following languages on $\{a,b\}.$ For each problem, define a set of appropriate macroinstructions that you feel are reasonably easy to implement. Then use them for the solution. $L = \{a^n : n\text{ is a prime number}\}.$
asked
Apr 9, 2019
in
Theory of Computation
by
Rishi yadav

11
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
10
Peter Linz Edition 5 Exercise 9.2 Question 5(d) (Page No. 245)
Provide a “highlevel” description for Turing machines that accept the following languages on $\{a,b\}$. For each problem, define a set of appropriate macroinstructions that you feel are reasonably easy to implement. Then use them for the solution. $L = \{a^nb^m : m = n^2,n\geq1\}.$
asked
Apr 9, 2019
in
Theory of Computation
by
Rishi yadav

15
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
11
Peter Linz Edition 5 Exercise 9.2 Question 5(c) (Page No. 245)
Provide a “highlevel” description for Turing machines that accept the following languages on $\{a,b\}.$ For each problem, define a set of appropriate macroinstructions that you feel are reasonably easy to implement. Then use them for the solution. $\text{The complement of the language in }L = \{ww^R\}.$
asked
Apr 9, 2019
in
Theory of Computation
by
Rishi yadav

41
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
12
Peter Linz Edition 5 Exercise 9.2 Question 5(b) (Page No. 245)
Provide a “highlevel” description for Turing machines that accept the following languages on $\{a,b\}.$ For each problem, define a set of appropriate macroinstructions that you feel are reasonably easy to implement. Then use them for the solution. $L = \{w_1w_2: w_1 \neq w_2: w_1 = w_2\}.$
asked
Apr 9, 2019
in
Theory of Computation
by
Rishi yadav

16
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
13
Peter Linz Edition 5 Exercise 9.2 Question 5(a) (Page No. 244)
Provide a “highlevel” description for Turing machines that accept the following languages on $\{a,b\}.$ For each problem, define a set of appropriate macroinstructions that you feel are reasonably easy to implement. Then use them for the solution. $L = \{ww^R\}.$
asked
Apr 9, 2019
in
Theory of Computation
by
Rishi yadav

11
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
14
Peter Linz Edition 5 Exercise 9.2 Question 4 (Page No. 244)
Use a block diagram to sketch the implementation of a function f defined for all $w_1,w_2,w_3\in \{1\}^+$ by $f(w_1,w_2,w_3) = i,$ where $i$ is such that $w_i = \text{max}(w_1,w_2,w_3)$ if no two $w’s$ have the same length, and $i=0$ otherwise.
asked
Apr 9, 2019
in
Theory of Computation
by
Rishi yadav

6
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
15
Peter Linz Edition 5 Exercise 9.2 Question 3(d) (Page No. 244)
Using adders, subtracters, comparers, copies or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ $f(n) = n!,$
asked
Apr 9, 2019
in
Theory of Computation
by
Rishi yadav

43
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
16
Peter Linz Edition 5 Exercise 9.2 Question 3(e) (Page No. 244)
Using adders, subtracters, comparers, copiers or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ $f(n) = n^{n!},$
asked
Apr 9, 2019
in
Theory of Computation
by
Rishi yadav

24
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
17
Peter Linz Edition 5 Exercise 9.2 Question 3(c) (Page No. 244)
Using adders, subtracters, comparers, copies or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ $f(n) = 2^n,$
asked
Apr 9, 2019
in
Theory of Computation
by
Rishi yadav

20
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
18
Peter Linz Edition 5 Exercise 9.2 Question 3(b) (Page No. 244)
Using adders, subtracters, comparers, copies or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ $f(n) = n^5,$
asked
Apr 9, 2019
in
Theory of Computation
by
Rishi yadav

17
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
19
Peter Linz Edition 5 Exercise 9.2 Question 3(a) (Page No. 244)
Using adders, subtracters, comparers, copies or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ $f(n) = n(n+1),$
asked
Apr 9, 2019
in
Theory of Computation
by
Rishi yadav

20
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
20
Peter Linz Edition 5 Exercise 9.2 Question 2 (Page No. 244)
Establish a convention for representing positive and negative integers in unary notation. With your convention, sketch the construction of a subtracter for computing $xy.$
asked
Apr 9, 2019
in
Theory of Computation
by
Rishi yadav

10
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
21
Peter Linz Edition 5 Exercise 9.2 Question 1 (Page No. 244)
$\text{Example}:$ Design a Turing machine that multiples two positive integers in unary notation. Write out the complete solution to Example.
asked
Apr 9, 2019
in
Theory of Computation
by
Rishi yadav

14
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
22
Peter Linz Edition 5 Exercise 9.1 Question 19 (Page No. 240)
You may have noticed that all the examples in these sections had only one final state. Is it generally true that for any Turing machine, there exists another one with only one final state that accepts the same language$?$
asked
Apr 9, 2019
in
Theory of Computation
by
Rishi yadav

10
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
proof
0
votes
0
answers
23
Peter Linz Edition 5 Exercise 9.1 Question 18 (Page No. 240)
$\text{Example}:$ Given two positive integers $x$ and $y$, design a Turing machine that computes $x+y$. Sketch how Example could be solved if $x$ and $y$ were represented in decimal.
asked
Apr 6, 2019
in
Theory of Computation
by
Rishi yadav

30
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
24
Peter Linz Edition 5 Exercise 9.1 Question 17 (Page No. 239)
$\text{Example}:$ Given two positive integers $x$ and $y,$ design a Turing machine that computes $x+y$. Suppose that in Example we had decided to represent $x$ and $y$ in binary. Write a Turing machine program for doing the indicated computation in this representation
asked
Apr 6, 2019
in
Theory of Computation
by
Rishi yadav

20
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
25
Peter Linz Edition 5 Exercise 9.1 Question 16 (Page No. 239)
$\text{Example}:$ Let $x$ and $y$ be two positive integers represented in unary notation. Construct a Turing machine that will halt in a final state $q_y$ if $x\geq y,$ and that will halt in a nonfinal state $q_n$ if $x < y.$ More ... $q_0w(x)0w(y) \vdash^* q_nw(x)0w(y)$ if $x < y$, Complete all the details in Example
asked
Apr 6, 2019
in
Theory of Computation
by
Rishi yadav

34
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
26
Peter Linz Edition 5 Exercise 9.1 Question 15 (Page No. 239)
$\text{Example}:$ Design a Turing machine that copies strings of $1’s$. More precisely, find a machine that performs the computation $q_0w \vdash^* q_fww,$ for any $w\in\{1\}^+$. Give convincing arguments that the Turing machine in Example does in fact carry out the indicated computation$.$
asked
Apr 6, 2019
in
Theory of Computation
by
Rishi yadav

16
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
27
Peter Linz Edition 5 Exercise 9.1 Question 14 (Page No. 239
$\text{Example}:$ Design a Turing machine that copies strings of $1's$. More precisely, find a machine that performs the computation $q_0w \vdash^* q_fww,$ for any $w\in\{1\}^+$. Give the sequence of instantaneous ... through when presented with the input $111$. What happens when this machine is started with $110$ on its tape$?$
asked
Apr 6, 2019
in
Theory of Computation
by
Rishi yadav

21
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
28
Peter Linz Edition 5 Exercise 9.1 Question 13 (Page No. 239)
$\text{Example}:$ Design a Turing machine that accepts $L = \{a^nb^nc^n:n\geq 1\}$. Write out a complete solution for Example.
asked
Apr 6, 2019
in
Theory of Computation
by
Rishi yadav

15
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
29
Peter Linz Edition 5 Exercise 9.1 Question 12 (Page No. 239)
Design a Turing machine $\Gamma = \{0,1,\square\}$ that, when started on any cell containing a blank or $a\space 1$, will halt if and only if its tape has a $0$ somewhere it.
asked
Apr 6, 2019
in
Theory of Computation
by
Rishi yadav

23
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
30
Peter Linz Edition 5 Exercise 9.1 Question 11(f) (Page No. 239)
Design Turing machines to compute the following functions for $x$ and $y$ positive integers represented in unary. $f(x) = \lfloor{\frac{x}{2}}\rfloor,$ where $\lfloor{\frac{x}{2}}\rfloor,$ denotes the largest integer less than or equal to $\frac{x}{2}.$
asked
Apr 6, 2019
in
Theory of Computation
by
Rishi yadav

18
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
Page:
« prev
1
2
3
4
5
6
7
8
9
...
16
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
How am I preparing
PGEE 2020 (CSE) Experience
IIT Tirupati MS Interview 2020
IIT Bombay Mtech RA  interview experience (2020)
Subjects
All categories
General Aptitude
(2k)
Engineering Mathematics
(8.2k)
Digital Logic
(2.9k)
Programming and DS
(5k)
Algorithms
(4.4k)
Theory of Computation
(6.2k)
Compiler Design
(2.2k)
Operating System
(4.6k)
Databases
(4.2k)
CO and Architecture
(3.4k)
Computer Networks
(4.2k)
Non GATE
(1.2k)
Others
(1.5k)
Admissions
(595)
Exam Queries
(562)
Tier 1 Placement Questions
(23)
Job Queries
(71)
Projects
(19)
Unknown Category
(1k)
Recent questions tagged turingmachine
Recent Blog Comments
........
After getting so many mails from you...
Refund will be given for such cases if applied...
@sreejit007 they don't publish any cutoff or...
@ranjanabhi Can you please elaborate what did...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,315
questions
60,430
answers
201,762
comments
95,241
users