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 9.1 Question 11(d) (Page No. 239)
Design Turing machines to compute the following functions for $x$ and $y$ positive integers represented in unary $f(x) =\frac{x}{2},$ if $x$ is even, $ = \frac{x+1}{2},$ if $x$ is odd.
asked
Apr 6
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

10
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
2
Peter Linz Edition 5 Exercise 9.1 Question 11(c) (Page No. 239)
Design Turing machines to compute the following functions for $x$ and $y$ positive integers represented in unary $f(x,y) = 2x+3y$.
asked
Apr 6
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

12
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
3
Peter Linz Edition 5 Exercise 9.1 Question 11(b) (Page No. 239)
Design Turing machines to compute the following functions for $x$ and $y$ positive integers represented in unary. $f(x,y) = xy,$ $x>y,$ $= 0,$ $x\leq y$.
asked
Apr 6
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

8
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
4
Peter Linz Edition 5 Exercise 9.1 Question 11(a) (Page No. 239)
Design Turing machines to compute the following functions for $x$ and $y$ positive integers represented in unary. $f(x) = 3x$
asked
Apr 6
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

22
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
5
Peter Linz Edition 5 Exercise 9.1 Question 10 (Page No. 239)
Design a Turing machine that finds the middle of a string of even length. Specifically, if $w = a_1a_2...a_na_{n+1}...a_{2n},$ with $a_i\in\Sigma,$ the Turing machine should produce $\widehat{w} = a_1a_2...a_nca_{n+1}...a_{2n},$ where $c\in\Gamma\Sigma$.
asked
Apr 6
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

6
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
6
Peter Linz Edition 5 Exercise 9.1 Question 9 (Page No. 239)
Construct a Turing machine to compute the function $f(w) = w^R$, where $w\in \{0,1\}^+$.
asked
Apr 6
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

5
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
7
Peter Linz Edition 5 Exercise 9.1 Question 8 (Page No. 239)
Design a Turing machine that accepts the language. $L = \Big\{ww:w\in \{a,b\}^+\Big\}$.
asked
Apr 6
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

9
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
8
Peter Linz Edition 5 Exercise 9.1 Question 7(h) (Page No. 239)
Construct Turing machines that will accept the following languages on $\{a,b\}$ $L = \{a^nb^{2n}:n\geq 0\}$.
asked
Apr 6
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

11
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
9
Peter Linz Edition 5 Exercise 9.1 Question 7(g) (Page No. 239)
Construct Turing machines that will accept the following languages on $\{a,b\}$. $L = \{a^nb^na^nb^n:n\geq0\}$.
asked
Apr 6
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

2
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
10
Peter Linz Edition 5 Exercise 9.1 Question 7(f) (Page No. 238)
Construct Turing machines that will accept the following languages on $\{a,b\}$. $L = \{a^nb^ma^{n+m}:n\geq0,m\geq1\}$.
asked
Apr 6
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

8
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
11
Peter Linz Edition 5 Exercise 9.1 Question 7(e) (Page No. 238)
Construct Turing machines that will accept the following languages on $\{a,b\}$ $L = \{w:n_a(w) = n_b(w)\}$.
asked
Apr 6
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

7
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
12
Peter Linz Edition 5 Exercise 9.1 Question 7(d) (Page No. 238)
Construct Turing machines that will accept the following languages on $\{a,b\}$. $L = \{a^nb^m:n\geq1,n\neq m\}$.
asked
Apr 6
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 9.1 Question 7(c) (Page No. 238)
Construct Turing machines that will accept the following languages on $\{a,b\}$. $L = \{w:w \text{ is a multiple of 3}\}$.
asked
Apr 6
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

11
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
14
Peter Linz Edition 5 Exercise 9.1 Question 7(b) (Page No. 238)
Construct Turing machines that will accept the following languages on $\{a,b\}$ $L = \{w:w \text{ is even }\}$.
asked
Apr 3
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

6
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
15
Peter Linz Edition 5 Exercise 9.1 Question 7(a) (Page No. 238)
Construct Turing machines that will accept the following languages on $\{a,b\}$. $L = L(aba^*b)$.
asked
Apr 3
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

22
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
16
Peter Linz Edition 5 Exercise 9.1 Question 6 (Page No. 238)
$\text{Example}:$ Design a Turing machine that copies strings of $1’s$. More precisely, find a machine that performs the computation $q_0q\vdash^*q_fww,$ for any $w\in\{1\}^+$. What happens in Example if the string $w$ contains any symbol other than $1?$
asked
Apr 3
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

2
views
peterlinz
theoryofcomputation
turingmachine
0
votes
1
answer
17
Peter Linz Edition 5 Exercise 9.1 Question 5 (Page No. 238)
What language is accepted by the Turing machine whose transition graph is in the figure below$?$
asked
Apr 3
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

27
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
18
Peter Linz Edition 5 Exercise 9.1 Question 4 (Page No. 238)
$\text{Example}:$ For $\Sigma = \{a,b\}$ design a Turing machine that accepts $L = \{a^nb^n:n\geq 1\}$. Is there any input for which the Turing machine in Example goes into an infinite loop$?$
asked
Apr 3
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

3
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
19
Peter Linz Edition 5 Exercise 9.1 Question 3 (Page No. 238)
$\text{Example}:$ For $\Sigma = \{a,b\}$ design a Turing machine that accepts $L = \{a^nb^n:n\geq 1\}$. Determine what the Turing machine in Example does when presented with the inputs $aba$ and $aaabbbb$.
asked
Apr 3
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

5
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
20
Peter Linz Edition 5 Exercise 9.1 Question 2 (Page No. 238)
Design a Turing machine with no more than three states that accept the language $L(a(a+b)^*)$. Assume that $\Sigma = \{a,b\}$. Is it possible to do this with a twostate machine$?$
asked
Apr 3
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

2
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
21
Peter Linz Edition 5 Exercise 9.1 Question 1 (Page No. 238)
Write a Turing machine simulator in some higherlevel programming language. Such a simulator should accept as input the description of any Turing machine, together with an initial configuration, and should produce as output the result of the computation.
asked
Apr 3
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

4
views
peterlinz
theoryofcomputation
turingmachine
difficult
0
votes
0
answers
22
Peter Linz Edition 5 Exercise 10.5 Question 6,7 (Page No. 276)
$\text{Exercise}:6$ ... above exercise to show that any contextfree language not containing $\lambda$ is accepted by some linear bounded automaton.
asked
Apr 3
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

11
views
peterlinz
theoryofcomputation
turingmachine
proof
0
votes
0
answers
23
Peter Linz Edition 5 Exercise 10.5 Question 5 (Page No. 276)
$\text{Example}:$ Find a linear bounded automaton that accepts the language $L = \{a^{n!}:n\geq0\}$. Find a lba for the complement of the language in Example, assuming that $\Sigma = \{a,b\}$.
asked
Apr 3
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

9
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
24
Peter Linz Edition 5 Exercise 10.5 Question 4(f) (Page No. 276)
Find linear bounded automata for the following languages. $L =\Big \{www^R:w\in \{a,b\}^+\Big\}$.
asked
Apr 3
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

15
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
25
Peter Linz Edition 5 Exercise 10.5 Question 4(e) (Page No. 276)
Find linear bounded automata for the following languages. $L = \Big\{w^n : w\in\{a,b\}^+,n\geq2\Big\}$.
asked
Apr 3
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

8
views
peterlinz
theoryofcomputation
turingmachine
+1
vote
0
answers
26
Peter Linz Edition 5 Exercise 10.5 Question 4(d) (Page No. 275)
Find linear bounded automata for the following language. $L = \Big\{ww:w\in\{a,b\}^+\Big\}$.
asked
Apr 3
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

19
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
27
Peter Linz Edition 5 Exercise 10.5 Question 4(c) (Page No. 275)
Find linear bounded automata for the following language. $L = \{a^n: \text{n is not a prime number}\}$.
asked
Apr 3
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

13
views
peterlinz
theoryofcomputation
turingmachine
proof
0
votes
0
answers
28
Peter Linz Edition 5 Exercise 10.5 Question 4(b) (Page No. 275)
Find linear bounded automata for the following language. $L = \{a^n: \text{n is a prime number}\}$.
asked
Apr 3
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

4
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
29
Peter Linz Edition 5 Exercise 10.5 Question 4(a) (Page No. 275)
Find linear bounded automata for the following language. $L = \{a^n: n = m^2,m\geq 1\}$
asked
Apr 3
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

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

3
views
peterlinz
theoryofcomputation
turingmachine
proof
Page:
« prev
1
2
3
4
5
6
7
8
9
10
...
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
Even In 2019 my 16 questions goes for negative...
It's a question not a post..
i also don't have any pdf, actually, I added the...
i don't have , if you have upload it
@mohan123 Do you have all standard book...
50,647
questions
56,492
answers
195,470
comments
100,766
users