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 9.1 Question 11(e) (Page No. 239)
Design Turing machines to compute the following functions for $x$ and $y$ positive integers represented in unary. $f(x) = x \text { mod } 5. $
asked
Apr 6, 2019
in
Theory of Computation
by
Rishi yadav

16
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
2
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, 2019
in
Theory of Computation
by
Rishi yadav

18
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
3
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, 2019
in
Theory of Computation
by
Rishi yadav

35
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
4
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, 2019
in
Theory of Computation
by
Rishi yadav

13
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
5
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, 2019
in
Theory of Computation
by
Rishi yadav

33
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
6
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, 2019
in
Theory of Computation
by
Rishi yadav

16
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
7
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, 2019
in
Theory of Computation
by
Rishi yadav

9
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
8
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, 2019
in
Theory of Computation
by
Rishi yadav

14
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
9
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, 2019
in
Theory of Computation
by
Rishi yadav

14
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
10
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, 2019
in
Theory of Computation
by
Rishi yadav

11
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
11
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, 2019
in
Theory of Computation
by
Rishi yadav

14
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
12
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, 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.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, 2019
in
Theory of Computation
by
Rishi yadav

10
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
14
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, 2019
in
Theory of Computation
by
Rishi yadav

21
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
15
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, 2019
in
Theory of Computation
by
Rishi yadav

12
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
16
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, 2019
in
Theory of Computation
by
Rishi yadav

72
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
17
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, 2019
in
Theory of Computation
by
Rishi yadav

10
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
1
answer
18
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, 2019
in
Theory of Computation
by
Rishi yadav

41
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
19
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, 2019
in
Theory of Computation
by
Rishi yadav

7
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
20
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, 2019
in
Theory of Computation
by
Rishi yadav

11
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
21
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, 2019
in
Theory of Computation
by
Rishi yadav

6
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
22
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, 2019
in
Theory of Computation
by
Rishi yadav

18
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
difficult
0
votes
0
answers
23
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, 2019
in
Theory of Computation
by
Rishi yadav

18
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
proof
0
votes
0
answers
24
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, 2019
in
Theory of Computation
by
Rishi yadav

13
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
25
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, 2019
in
Theory of Computation
by
Rishi yadav

30
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
26
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, 2019
in
Theory of Computation
by
Rishi yadav

16
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
+1
vote
0
answers
27
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, 2019
in
Theory of Computation
by
Rishi yadav

99
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
28
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, 2019
in
Theory of Computation
by
Rishi yadav

30
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
proof
0
votes
0
answers
29
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, 2019
in
Theory of Computation
by
Rishi yadav

31
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
0
votes
0
answers
30
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, 2019
in
Theory of Computation
by
Rishi yadav

12
views
peterlinz
peterlinzedition5
theoryofcomputation
turingmachine
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
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...
ISI 2019 : Aarushi Aiyyar's answer to How do...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,315
questions
60,438
answers
201,786
comments
95,269
users