The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
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
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged turingmachine
Turing Machine Notes
0
votes
0
answers
1
Peter Linz Edition 5 Exercise 11.3 Question 6 (Page No. 296)
Without explicitly constructing it, show that there exists a contextsensitive grammar for the language $L=\{www^R: w,u\in\{a,b\}^+,w\gequ\}$.
asked
3 days
ago
in
Theory of Computation
by
Rishi yadav
Boss
(
10.1k
points)

5
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
2
Peter Linz Edition 5 Exercise 11.3 Question 5 (Page No. 296)
$\text{Theorem}:$ Every contextsensitive language $L$ is recursive. For $m$ in Theorem, give explicit bounds for $m$ as a function of $w$ and $V\cup T$.
asked
3 days
ago
in
Theory of Computation
by
Rishi yadav
Boss
(
10.1k
points)

3
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
3
Peter Linz Edition 5 Exercise 11.3 Question 4 (Page No. 296)
Show that the family of contextsensitive languages is closed under reversal.
asked
3 days
ago
in
Theory of Computation
by
Rishi yadav
Boss
(
10.1k
points)

3
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
proof
0
votes
0
answers
4
Peter Linz Edition 5 Exercise 11.3 Question 3 (Page No. 296)
Show that the family of contextsensitive languages is closed under union.
asked
3 days
ago
in
Theory of Computation
by
Rishi yadav
Boss
(
10.1k
points)

3
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
proof
0
votes
0
answers
5
Peter Linz Edition 5 Exercise 11.3 Question 2 (Page No. 296)
Find contextsensitive grammars for the following languages. $(a)$ $L=\{w: n_a(w) = n_b(w) = n_c(w)\}$. $(b)$ $L=\{w: n_a(w) = n_b(w) < n_c(w)\}$.
asked
3 days
ago
in
Theory of Computation
by
Rishi yadav
Boss
(
10.1k
points)

2
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
difficult
0
votes
0
answers
6
Peter Linz Edition 5 Exercise 11.3 Question 1 (Page No. 296)
Find the contextsensitive grammars for the following languages. $\text{(a)}$ $L=\{a^{n+1}b^nc^{n1} : n\geq 1\}$. $\text{(b)}$ $L=\{a^{n}b^nc^{2n} : n\geq 1\}$. $\text{(c)}$ $L=\{a^{n}b^mc^{n}d^m : n\geq 1, m\geq1\}$. $\text{(d)}$ $L=\{ww : w\in \{a,b\}^+\}$. $\text{(e)}$ $L=\{a^{n}b^nc^{n}d^m : n\geq 1\}$.
asked
3 days
ago
in
Theory of Computation
by
Rishi yadav
Boss
(
10.1k
points)

2
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
difficult
0
votes
0
answers
7
Peter Linz Edition 5 Exercise 11.2 Question 9 (Page No. 290,291)
A grammar $G = (V, T, S, P)$ is called $\text{unrestricted }$ if all the production are of the form $u\rightarrow v$, where $u$ is nit $(V\cup T)^+$ and $v$ is int $(V\cup T)^*$ Some authors give ... the same as the one we use, in the sense that for every grammar of one type, there is an equivalent grammar of the other type.
asked
3 days
ago
in
Theory of Computation
by
Rishi yadav
Boss
(
10.1k
points)

3
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
8
Peter Linz Edition 5 Exercise 11.2 Question 8 (Page No. 290)
Every unrestricted grammar there exists an equivalent unrestricted grammar, all of whose productions have the form $u\rightarrow v,$ with $u,v\in (V \cup T)^+$ and $u \leq v$, or $A\rightarrow\lambda$ with $A\in V$ Show that the conclusion still holds if we add the further conditions $u\leq2$ and $v\leq2$
asked
3 days
ago
in
Theory of Computation
by
Rishi yadav
Boss
(
10.1k
points)

3
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
9
Peter Linz Edition 5 Exercise 11.2 Question 7 (Page No. 290)
Show that for every unrestricted grammar there exists an equivalent unrestricted grammar, all of whose productions have the form $u\rightarrow v,$ with $u,v\in (V \cup T)^+$ and $u \leq v$, or $A\rightarrow\lambda$ with $A\in V$
asked
3 days
ago
in
Theory of Computation
by
Rishi yadav
Boss
(
10.1k
points)

3
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
10
Peter Linz Edition 5 Exercise 11.2 Question 6 (Page No. 290)
$\text{Theorem}:$ For every recursively enumerable language $L$, there exists an unrestricted grammar $G$, such that $L=L(G)$. Construct a Turing machine for $L(01(01)^*)$, then find an unrestricted grammar for it using the construction in Theorem. Give a derivation for $0101$ using the resulting grammar.
asked
3 days
ago
in
Theory of Computation
by
Rishi yadav
Boss
(
10.1k
points)

3
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
11
Peter Linz Edition 5 Exercise 11.2 Question 5 (Page No. 290)
$\text{Theorem}:$ For every recursively enumerable language $L$, there exists an unrestricted grammar $G$, such that $L = L(G)$. Give the details of the proof of the Theorem.
asked
3 days
ago
in
Theory of Computation
by
Rishi yadav
Boss
(
10.1k
points)

2
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
12
Peter Linz Edition 5 Exercise 11.2 Question 4 (Page No. 290)
Prove that constructed grammar cannot generate any sentence with $a\space b$ in it. $S\rightarrow S_1B,$ $S_1\rightarrow aS_1b,$ $bB\rightarrow bbbB,$ $aS_1b\rightarrow aa,$ $B\rightarrow \lambda$
asked
3 days
ago
in
Theory of Computation
by
Rishi yadav
Boss
(
10.1k
points)

4
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
13
Peter Linz Edition 5 Exercise 11.2 Question 3 (Page No. 290)
Consider a variation on grammars in which the starting point of any derivation can be a finite set of strings, rather than a single variable. Formalize this concept, then investigate how such grammars relate to the unrestricted grammars we have used here.
asked
3 days
ago
in
Theory of Computation
by
Rishi yadav
Boss
(
10.1k
points)

3
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
14
Peter Linz Edition 5 Exercise 11.2 Question 2 (Page No. 290)
What difficulties would arise if we allowed the empty string as the left side of a production in an unrestricted grammar$?$
asked
3 days
ago
in
Theory of Computation
by
Rishi yadav
Boss
(
10.1k
points)

4
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
15
Peter Linz Edition 5 Exercise 11.2 Question 1 (Page No. 290)
What language does the unrestricted grammar $S\rightarrow S_1B,$ $S_1\rightarrow aS_1b,$ $bB\rightarrow bbbB,$ $aS_1b\rightarrow aa,$ $B\rightarrow \lambda$ derive$?$
asked
3 days
ago
in
Theory of Computation
by
Rishi yadav
Boss
(
10.1k
points)

4
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
proof
0
votes
1
answer
16
Peter Linz Edition 5 Exercise 11.1 Question 19 (Page No. 284)
Show that the set of all irrational numbers is not countable.
asked
4 days
ago
in
Theory of Computation
by
Rishi yadav
Boss
(
10.1k
points)

28
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
17
Peter Linz Edition 5 Exercise 11.1 Question 18 (Page No. 284)
$\text{Theorem}:$ Let $S$ be an infinite countable set. Then its powerset $2^S$ is not countable. Why does the argument in Theorem fail when $S$ is finite$?$
asked
4 days
ago
in
Theory of Computation
by
Rishi yadav
Boss
(
10.1k
points)

13
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
18
Peter Linz Edition 5 Exercise 11.1 Question 17 (Page No. 284)
Let $S_1$ be a countable set, $S_2$ a set that is not countable, and $S_1 \subset S_2$. Show that $S_2$ must then contain an infinite number of elements that are not in $S_1$. Show that in fact $S_2S_1$ cannot be countable.
asked
4 days
ago
in
Theory of Computation
by
Rishi yadav
Boss
(
10.1k
points)

11
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
19
Peter Linz Edition 5 Exercise 11.1 Question 16 (Page No. 284)
Let $S_1$ be a countable set, $S_2$ a set that is not countable, and $S_1 \subset S_2$. Show that $S_2$ must then contain an infinite number of elements that are not in $S_1$.
asked
4 days
ago
in
Theory of Computation
by
Rishi yadav
Boss
(
10.1k
points)

14
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
20
Peter Linz Edition 5 Exercise 11.1 Question 15 (Page No. 284)
$\text{Theorem}:$ There exists a recursively enumerable language whose complement is not recursively enumerable. Choose a particular encoding for Turing machines, and with it, find one element of the languages $\bar{L}$ in Theorem
asked
4 days
ago
in
Theory of Computation
by
Rishi yadav
Boss
(
10.1k
points)

10
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
21
Peter Linz Edition 5 Exercise 11.1 Question 14 (Page No. 284)
If $L$ is recursive, is it necessarily true that $L^+$ is also recursive$?$
asked
4 days
ago
in
Theory of Computation
by
Rishi yadav
Boss
(
10.1k
points)

9
views
theoryofcomputation
proof
recursiveandrecursivelyenumerablelanguages
turingmachine
peterlinz
0
votes
0
answers
22
Peter Linz Edition 5 Exercise 11.1 Question 13 (Page No. 284)
Suppose that $L$ is such that there exists a Turing machine that enumerates the elements of $L$ in proper order. Show that this means that $L$ is recursive.
asked
4 days
ago
in
Theory of Computation
by
Rishi yadav
Boss
(
10.1k
points)

5
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
2
answers
23
Peter Linz Edition 5 Exercise 11.1 Question 12 (Page No. 284)
Let $L_1$ be recursive and $L_2$ recursively enumerable. Show that $L_2L_1$ is necessarily recursively enumerable.
asked
4 days
ago
in
Computer Networks
by
Rishi yadav
Boss
(
10.1k
points)

7
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
24
Peter Linz Edition 5 Exercise 11.1 Question 11 (Page No. 284)
Prove that the complement of a contextfree language must be recursive.
asked
4 days
ago
in
Computer Networks
by
Rishi yadav
Boss
(
10.1k
points)

4
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
25
Peter Linz Edition 5 Exercise 11.1 Question 10 (Page No. 284)
Is the family of recursive languages closed under concatenation$?$
asked
4 days
ago
in
Computer Networks
by
Rishi yadav
Boss
(
10.1k
points)

10
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
26
Peter Linz Edition 5 Exercise 11.1 Question 9 (Page No. 284)
Show that the families of recursively enumerable and recursive languages are closed under reversal.
asked
4 days
ago
in
Computer Networks
by
Rishi yadav
Boss
(
10.1k
points)

5
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
27
Peter Linz Edition 5 Exercise 11.1 Question 8 (Page No. 284)
Show that the family of recursive languages is closed under union and intersection.
asked
4 days
ago
in
Computer Networks
by
Rishi yadav
Boss
(
10.1k
points)

4
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
28
Peter Linz Edition 5 Exercise 11.1 Question 7 (Page No. 284)
Is the family of recursively enumerable languages closed under intersection$?$
asked
4 days
ago
in
Computer Networks
by
Rishi yadav
Boss
(
10.1k
points)

6
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
29
Peter Linz Edition 5 Exercise 11.1 Question 6 (Page No. 284)
Show that the family of recursively enumerable languages is closed under union.
asked
4 days
ago
in
Computer Networks
by
Rishi yadav
Boss
(
10.1k
points)

8
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
30
Peter Linz Edition 5 Exercise 11.1 Question 5 (Page No. 284)
Show that if a language is not recursively enumerable, its complement cannot be recursive.
asked
4 days
ago
in
Computer Networks
by
Rishi yadav
Boss
(
10.1k
points)

3
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
Page:
1
2
3
4
5
6
...
10
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
IIT Gandhinagar review
Is DAIICT good for doing MTech ?
AIR175 : GO is enough
GATE 2019 My reasoned routine. (AIR 558)
if i can you also can
Follow @csegate
Recent questions tagged turingmachine
Recent Blog Comments
congrats man!!! u surely need guts to leave job...
You won't get M.Tech degree then
I have generic query , not just about iit gn but...
Thank you Abhishek
Heartliest Congratulation Abhishek Bhai. This was...
48,515
questions
52,763
answers
183,377
comments
68,235
users