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 recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
1
Michael Sipser Edition 3 Exercise 3 Question 6 (Page No. 188)
In Theorem $3.21$, we showed that a language is Turingrecognizable iff some enumerator enumerates it. Why didn't we use the following simpler algorithm for the forward direction of the proof? As before, $s_{1}, s_{2},\dots $ is a list of all strings in ... $i = 1,2,3,\dots.$ Run $M$ on $s_{i}.$ If it accepts, print out $s_{i}."$
asked
Oct 15
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
52.9k
points)

4
views
michaelsipser
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
proof
0
votes
0
answers
2
Ullman (TOC) Edition 3 Exercise 9.3 Question 8 (Page No. 401)
Tell whether each of the following are recursive, REbutnotrecursive, or nonRE. The set of all $TM$ codes for $TM's$ that halt on every input. The set of all $TM$ codes for $TM's$ ... that halt on at least one input. The set of all $TM$ codes for $TM's$ that fail to halt on at least one input.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
52.9k
points)

18
views
ullman
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
descriptive
0
votes
0
answers
3
Ullman (TOC) Edition 3 Exercise 9.3 Question 7 (Page No. 400  401)
Show that the following problems are not recursively enumerable: The set of pairs $(M,w)$ such that $TM \ M$, started with input $w$, does not halt. The set of pairs $(M_{1},M_{2})$ such that $L(M_{1}\cap L_(M_{2})=\phi$. ... $TM's$.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
52.9k
points)

12
views
ullman
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
descriptive
0
votes
0
answers
4
Ullman (TOC) Edition 3 Exercise 9.3 Question 5 (Page No. 400)
Let $L$ be the language consisting of pairs of $TM$ codes plus an integer, $(M_{1},M_{2},k)$, such that $L(M_{1})\cap L(M_{2})$ contains at least $k$ strings. Show that $L$ is $RE$, but recursive.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
52.9k
points)

11
views
ullman
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
descriptive
0
votes
0
answers
5
Ullman (TOC) Edition 3 Exercise 9.2 Question 6 (Page No. 392)
We have not discussed closure properties of the recursive languages or the RE languages other than our discussion of complementation in Section $9.2.2.$ Tell whether the recursive languages and/or the RE ... , constructions to show closure. Union. Intersection. Concatenation. Kleene closure(star). Homomorphism. Inverse homomorphism.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
52.9k
points)

5
views
ullman
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
descriptive
0
votes
0
answers
6
Ullman (TOC) Edition 3 Exercise 9.2 Question 5 (Page No. 392)
Let $L$ be recursively enumerable and let $\overline{L}$ be nonRE. Consider the language $L' = \left\{0w\mid w\ \text{is in}\ L \right\}$ Can you say for certain whether $L'$ or its complement are recursive, RE, or nonRE? Justify your answer.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
52.9k
points)

8
views
ullman
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
descriptive
0
votes
0
answers
7
Ullman (TOC) Edition 3 Exercise 9.2 Question 4 (Page No. 391)
Let $L_{1},L_{2},\cdot\cdot\cdot,L_{k}$ be a collection of languages over alphbet $\Sigma$ such that: For all $i\neq j$, $L_{i}\cap L_{j}=\phi$ ... languages $L_{i}$, for $i=1,2,\cdot\cdot\cdot,k$ is recursively enumerable. Prove that each of the languages is therefore recursive.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
52.9k
points)

9
views
ullman
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
8
Ullman (TOC) Edition 3 Exercise 9.2 Question 3 (Page No. 391)
Informally describe multitape Turing machines that enumerate the following sets of integers, in the sense that started with blank tapes, it prints on one of its tapes $10^{i_{1}}10^{i_{2}}1\cdot\cdot\cdot$ ... $s$ steps, then we shall eventually discover each $M_{i}$ that accepts $w_{i}$ and enumerate $i$.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
52.9k
points)

4
views
ullman
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
descriptive
0
votes
1
answer
9
Self Doubt: Decidability
$L=\left \{< M_{1},M_{2}> \text{such that L}(M_{1})\prec L(M_{2}) \right \}$ is it recursive enumerable? here $L\left ( M_{1} \right )\prec L\left ( M_{2} \right )$ signifies language $L\left ( M_{1} \right )$ is reducible to $L\left ( M_{2} \right )$
asked
Jul 15
in
Theory of Computation
by
ajaysoni1924
Boss
(
10.5k
points)

133
views
theoryofcomputation
turingmachine
decidability
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
10
Self Doubt:Toc
asked
Jun 2
in
Theory of Computation
by
Hirak
Active
(
3.5k
points)

57
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
2
answers
11
Self Doubt:Automata
Intersection of Recursive and Recursively Enumerable language is____________________ ?
asked
Jun 2
in
Theory of Computation
by
Hirak
Active
(
3.5k
points)

68
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
12
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.2k
points)

7
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
13
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.2k
points)

3
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
14
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.2k
points)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

45
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
Page:
1
2
3
4
5
6
7
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
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Minimal Deterministic Finite Automata
To be aware of fake GATE test series
Standard Book Exercise Questions for Computer Science
Follow @csegate
Recent questions tagged recursiveandrecursivelyenumerablelanguages
Recent Blog Comments
Favorite is not working for blogs.. In favorites...
Favourite option does work. But list options...
Blog favorite button doesnt work?
@Arjun Sir can we have an option to save such...
Thanks Sir
50,666
questions
56,165
answers
193,790
comments
93,877
users