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
All Activity
Questions
Unanswered
Tags
Categories
Users
Ask a Question
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 recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
1
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
Boss
(
45.8k
points)

8
views
ullman
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
descriptive
0
votes
0
answers
2
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
Boss
(
45.8k
points)

7
views
ullman
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
descriptive
0
votes
0
answers
3
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
Boss
(
45.8k
points)

4
views
ullman
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
descriptive
0
votes
0
answers
4
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
Boss
(
45.8k
points)

4
views
ullman
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
descriptive
0
votes
0
answers
5
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
Boss
(
45.8k
points)

4
views
ullman
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
descriptive
0
votes
0
answers
6
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
Boss
(
45.8k
points)

5
views
ullman
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
7
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
Boss
(
45.8k
points)

3
views
ullman
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
descriptive
0
votes
1
answer
8
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.2k
points)

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

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

63
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
11
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
(
10.9k
points)

6
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
12
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
(
10.9k
points)

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

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

23
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
15
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
(
10.9k
points)

5
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
16
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
(
10.9k
points)

9
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
proof
0
votes
0
answers
17
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
(
10.9k
points)

21
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
proof
0
votes
0
answers
18
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
(
10.9k
points)

4
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
difficult
0
votes
0
answers
19
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
(
10.9k
points)

11
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
difficult
0
votes
0
answers
20
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
(
10.9k
points)

5
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
21
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
(
10.9k
points)

5
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
22
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
(
10.9k
points)

5
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
23
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
(
10.9k
points)

6
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
24
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
(
10.9k
points)

10
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
25
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
(
10.9k
points)

6
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
26
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
(
10.9k
points)

4
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
27
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
(
10.9k
points)

8
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
28
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
(
10.9k
points)

7
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
proof
0
votes
1
answer
29
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
(
10.9k
points)

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

15
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
ISI MTECH CS 2019 INTERVIEW EXPERIENCE
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
Interview Experience at IISc
All subject Gate notes from Standard Books!!
Follow @csegate
Recent questions tagged recursiveandrecursivelyenumerablelanguages
Recent Blog Comments
Refund time depends on the payment mode ...
@Arjun Sir , when can i expect my refund in the...
This book is returned you can enable a pay now...
@Pranavcool The book stocks are over and no one...
@Lokesh Thats unfortunate. I have refunded you....
49,830
questions
54,806
answers
189,528
comments
80,824
users