The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
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 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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

16
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
2
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

13
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
3
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

20
views
peterlinz
theoryofcomputation
turingmachine
proof
0
votes
0
answers
4
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

4
views
peterlinz
theoryofcomputation
turingmachine
proof
0
votes
0
answers
5
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

5
views
peterlinz
theoryofcomputation
turingmachine
proof
0
votes
0
answers
6
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

7
views
theoryofcomputation
peterlinz
turingmachine
0
votes
0
answers
7
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

4
views
theoryofcomputation
peterlinz
turingmachine
0
votes
0
answers
8
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

3
views
theoryofcomputation
peterlinz
turingmachine
0
votes
0
answers
9
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

3
views
theoryofcomputation
peterlinz
turingmachine
0
votes
0
answers
10
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

5
views
theoryofcomputation
peterlinz
turingmachine
0
votes
0
answers
11
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

4
views
peterlinz
theoryofcomputation
turingmachine
proof
0
votes
0
answers
12
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

4
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
13
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

4
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
14
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

4
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
15
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

4
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
16
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

14
views
peterlinz
theoryofcomputation
turingmachine
proof
0
votes
0
answers
17
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

5
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
18
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

10
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
19
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

14
views
peterlinz
theoryofcomputation
turingmachine
difficult
0
votes
0
answers
20
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

9
views
peterlinz
theoryofcomputation
turingmachine
difficult
0
votes
0
answers
21
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

4
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
22
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

6
views
peterlinz
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
23
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

7
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
24
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

3
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
25
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

3
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
26
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

12
views
peterlinz
theoryofcomputation
turingmachine
proof
0
votes
0
answers
27
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

23
views
peterlinz
theoryofcomputation
turingmachine
proof
difficult
0
votes
0
answers
28
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

5
views
peterlinz
theoryofcomputation
turingmachine
proof
0
votes
0
answers
29
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

4
views
peterlinz
theoryofcomputation
turingmachine
proof
0
votes
0
answers
30
Peter Linz Edition 5 Exercise 10.1 Question 11 (Page No. 259)
Consider a Turing machine with a different decision process in which transitions are made if the current tape symbol is not one of the specified set. For example, $\delta(q_i,\{a,b\})=(q_j,c,R)$ will allow the ... neither $a$ nor $b$. Formalize this concept and show that this modification is equivalent to a standard Turing machine.
asked
Mar 28
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

20
views
peterlinz
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
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Follow @csegate
Recent questions tagged turingmachine
Recent Blog Comments
Really helpful sir Thanks a ton👍👍
Amazing work Sir
Not in my hands. Flipkart is showing my location...
Arjun sir, plz provide go book through...
@
[email protected]
Can this be updated?
50,644
questions
56,523
answers
195,608
comments
101,286
users