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
Peter Linz Edition 5 Exercise 10.5 Question 3 (Page No. 275)
Consider an offline Turing machine in which the input can be read only once, moving left to right, not rewritten. On its work tape, it can use at most n extra cells for work space, where n is fixed for all inputs. Show that such a machine is equivalent to a finite automaton.
asked
Apr 3, 2019
in
Theory of Computation
by
Rishi yadav

21
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
proof
0
votes
0
answers
2
Peter Linz Edition 5 Exercise 10.5 Question 2 (Page No. 275)
$\text{Example: }$Find a linear bounded automaton that accepts the language $L = \{a^{n!}:n\geq0\}$ Find a solution for Example that does not require track as scratch space.
asked
Apr 2, 2019
in
Theory of Computation
by
Rishi yadav

23
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
3
Peter Linz Edition 5 Exercise 10.5 Question 1 (Page No. 275)
$\text{Example: }$Find a linear bounded automaton that accepts the language $L = \{a^{n!}:n\geq0\}$ Give details for the solution of Example.
asked
Apr 2, 2019
in
Theory of Computation
by
Rishi yadav

33
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
4
Peter Linz Edition 5 Exercise 10.4 Question 9 (Page No. 273)
Show that the Cartesian product of a finite number of countable sets is countable.
asked
Apr 2, 2019
in
Theory of Computation
by
Rishi yadav

27
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
proof
0
votes
0
answers
5
Peter Linz Edition 5 Exercise 10.4 Question 8 (Page No. 273)
Suppose that $S_1$ and $S_2$ are countable sets. Show that then $S_1\cup S_2$ and $S_1 \times S_2$ are also countable.
asked
Apr 2, 2019
in
Theory of Computation
by
Rishi yadav

10
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
proof
0
votes
0
answers
6
Peter Linz Edition 5 Exercise 10.4 Question 7 (Page No. 273)
Show that the set of all triplets, $(i,j,k)$ with $i,j,k$ positive integers, is countable,
asked
Apr 2, 2019
in
Theory of Computation
by
Rishi yadav

8
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
proof
0
votes
0
answers
7
Peter Linz Edition 5 Exercise 10.4 Question 5 (Page No. 272)
Design a Turing machine that enumerates the following set in proper order $L = \{a^nb^n:n\geq 1\}$.
asked
Apr 2, 2019
in
Theory of Computation
by
Rishi yadav

11
views
theoryofcomputation
peterlinz
peterlinzedition5
turingmachine
0
votes
0
answers
8
Peter Linz Edition 5 Exercise 10.4 Question 4 (Page No. 272)
$\text{Exercise 3:}$ Sketch a Turing machine program that enumerates the set {0,1}+{0,1}+ in proper order. $\text{Exercise 4:}$ What is the index of $0^i1^j$ in Exercise 3$?$
asked
Apr 2, 2019
in
Theory of Computation
by
Rishi yadav

8
views
theoryofcomputation
peterlinz
peterlinzedition5
turingmachine
0
votes
0
answers
9
Peter Linz Edition 5 Exercise 10.4 Question 3 (Page No. 272)
Sketch a Turing machine program that enumerates the set $\{0,1\}^+$ in proper order.
asked
Apr 2, 2019
in
Theory of Computation
by
Rishi yadav

8
views
theoryofcomputation
peterlinz
peterlinzedition5
turingmachine
0
votes
0
answers
10
Peter Linz Edition 5 Exercise 10.4 Question 2 (Page No. 272)
Give a complete encoding, using the suggested method, for the Turing machine with $\delta(q_1,a_1) = (q_1,a_1,R)$, $\delta(q_1,a_2) = (q_3,a_1,L)$, $\delta(q_3,a_1) = (q_2,a_2,L)$,
asked
Apr 2, 2019
in
Theory of Computation
by
Rishi yadav

8
views
theoryofcomputation
peterlinz
peterlinzedition5
turingmachine
0
votes
0
answers
11
Peter Linz Edition 5 Exercise 10.4 Question 1 (Page No. 272)
Sketch an algorithm that examines a string in $\{0,1\}^+$ to determine whether or not it represents an encoded Turing machine.
asked
Apr 2, 2019
in
Theory of Computation
by
Rishi yadav

9
views
theoryofcomputation
peterlinz
peterlinzedition5
turingmachine
0
votes
0
answers
12
Peter Linz Edition 5 Exercise 10.3 Question 7 (Page No. 268)
$\text{Definition:}$ A $\text{nondeterministic pushdown acceptor (npda)}$ is defined by the septuple $M = (Q,\Sigma,\Gamma,\delta,q_0,z,F)$ where $Q$ ... being pushed on these two stacks. Show that the class of twostack automata is equivalent to the class of Turing machines.
asked
Apr 2, 2019
in
Theory of Computation
by
Rishi yadav

14
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
proof
0
votes
0
answers
13
Peter Linz Edition 5 Exercise 10.3 Question 6 (Page No. 268)
Design a nondeterministic Turing machine that accepts the language. $L = \{a^n: \text{n is not a prime number}\}$.
asked
Apr 2, 2019
in
Theory of Computation
by
Rishi yadav

17
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
14
Peter Linz Edition 5 Exercise 10.3 Question 5 (Page No. 268)
Write a simple program for a nondeterministic Turing machine that accepts the language $L = \Big\{ xww^Ry:x,y,w\in\{a,b\}^+,x\geq y\Big\}$. How would you solve this problem deterministically$?$
asked
Apr 2, 2019
in
Theory of Computation
by
Rishi yadav

8
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
15
Peter Linz Edition 5 Exercise 10.3 Question 4 (Page No. 268)
Outline how one would write a program for a nondeterministic Turing machine to accept the language $L=\{ww^Rw:w\in\{a,b\}^+\}$.
asked
Apr 2, 2019
in
Theory of Computation
by
Rishi yadav

9
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
16
Peter Linz Edition 5 Exercise 10.3 Question 3 (Page No. 268)
Write a program for a nondeterministic Turing machine that accepts the language. $L = \{ww:w\in \{a,b\}^+\}$ Contrast this with a deterministic solution.
asked
Apr 2, 2019
in
Theory of Computation
by
Rishi yadav

7
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
17
Peter Linz Edition 5 Exercise 10.3 Question 2 (Page No. 267)
Show how a twodimensional nondeterministic Turing machine can be simulated by a deterministic machine.
asked
Apr 2, 2019
in
Theory of Computation
by
Rishi yadav

28
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
proof
0
votes
0
answers
18
Peter Linz Edition 5 Exercise 10.3 Question 1 (Page No. 267)
Discuss in detail the simulation of a nondeterministic Turing machine by a deterministic one. Turing machine by a deterministic one. Indicate explicitly how new machines are created, how active machines are identified, and how machines that halt are removed from further consideration.
asked
Apr 2, 2019
in
Theory of Computation
by
Rishi yadav

12
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
19
Peter Linz Edition 5 Exercise 10.2 Question 10 (Page No. 264)
Write out a detailed program for the computation in considering the language $\{a^nb^n\}$. We described a laborious method by which this language can be accepted by a Turing machine with one tape. Using a twotape machine makes the ... an equal number of $a's$ and $b's$ without repeated backandforth movement of the readwrite head.
asked
Mar 30, 2019
in
Theory of Computation
by
Rishi yadav

24
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
20
Peter Linz Edition 5 Exercise 10.2 Question 6,7 (Page No. 264)
Exercise 6: Show that for every Turing machine there exists an equivalent standard Turing machine with no more than six states. Exercise 7: Reduce the number of required states in Exercise 6 above as far as you can (Hint: The smallest possible number is three)
asked
Mar 30, 2019
in
Theory of Computation
by
Rishi yadav

27
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
difficult
0
votes
0
answers
21
Peter Linz Edition 5 Exercise 10.2 Question 5 (Page No. 264)
A $\text{queue automaton}$ is an automaton in which the temporary storage is a queue. Assume that such a machine is an online machine, that is, it has no input file, with the string to be processed placed in ... of the computation. Give a formal definition of such an automaton, then investigate its power in relation to Turing machines.
asked
Mar 30, 2019
in
Theory of Computation
by
Rishi yadav

24
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
difficult
0
votes
0
answers
22
Peter Linz Edition 5 Exercise 10.2 Question 2 (Page No. 264)
A multihead Turing machine can be visualized as a Turing machine with a single tape and single control unit but with multiple, independent readwrite heads. Give a formal definition of a multihead Turing machine, and then show how much a machine can be simulated with a standard Turing machine.
asked
Mar 30, 2019
in
Theory of Computation
by
Rishi yadav

29
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
23
Peter Linz Edition 5 Exercise 10.2 Question 1 (Page No. 264)
Define what one might call a multitape offline Turing machine and describe how it can be simulated by a standard Turing machine.
asked
Mar 30, 2019
in
Theory of Computation
by
Rishi yadav

20
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
24
Peter Linz Edition 5 Exercise 11.4 Question 3 (Page No. 298)
Find two examples of languages that are deterministic contextfree but not linear.
asked
Mar 30, 2019
in
Theory of Computation
by
Rishi yadav

13
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
25
Peter Linz Edition 5 Exercise 11.4 Question 2 (Page No. 298)
Find two examples of languages that are linear but not deterministic contextfree.
asked
Mar 30, 2019
in
Theory of Computation
by
Rishi yadav

12
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
26
Peter Linz Edition 5 Exercise 11.4 Question 1 (Page No. 298)
Given examples that demonstrate that all the subset relations depicted in the figure are indeed proper ones.
asked
Mar 30, 2019
in
Theory of Computation
by
Rishi yadav

11
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
27
Peter Linz Edition 5 Exercise 10.2 Question 9 (Page No. 264)
Show that every computation that can be done by a standard Turing machine can be done a multitape machine with a stay option and at most two states.
asked
Mar 28, 2019
in
Theory of Computation
by
Rishi yadav

16
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
proof
0
votes
0
answers
28
Peter Linz Edition 5 Exercise 10.2 Question 8 (Page No. 264)
A counter is a stack with an alphabet of exactly two symbols a stack start symbol and a counter symbol. Only the counter symbol can be put on the stack or removed from it. A $\text{counter automaton}$ is a ... one or more counters as storage. Show that any Turing machines can be simulated using a counter automaton with four counters.
asked
Mar 28, 2019
in
Theory of Computation
by
Rishi yadav

33
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
proof
difficult
0
votes
0
answers
29
Peter Linz Edition 5 Exercise 10.2 Question 4 (Page No. 264)
Give a formal definition of a Turing machine with a single tape but multiple control units, each with a single readwrite head. Show how such a machine can be simulated with a multitape machine.
asked
Mar 28, 2019
in
Theory of Computation
by
Rishi yadav

9
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
proof
0
votes
0
answers
30
Peter Linz Edition 5 Exercise 10.2 Question 3 (Page No. 264)
Give a formal definition of a multiheadmultitape Turing machine. Then show how such a machine can be simulated by a standard Turing machine.
asked
Mar 28, 2019
in
Theory of Computation
by
Rishi yadav

9
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
proof
Page:
« prev
1
2
3
4
5
6
7
8
9
10
11
...
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
IITD MS CSE (Systems) Experience
IIT Bombay M.Tech. (RA)  Interview Experience
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
How am I preparing
PGEE 2020 (CSE) Experience
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
Very helpful. can't thank you enough! :) :)
@toxicdesire I don't remember the exact...
Will you please tell what they answered to your...
@commenter max marks for part A was 75. They did...
Hope you get selected bhaiya
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,345
questions
60,506
answers
201,910
comments
95,345
users