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
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
1
answer
1
Self Doubt:Toc
asked
Jun 2
in
Theory of Computation
by
Hirak
Active
(
3k
points)

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

52
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
3
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.5k
points)

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

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

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

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

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

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

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

4
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
difficult
0
votes
0
answers
11
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.5k
points)

10
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
difficult
0
votes
0
answers
12
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.5k
points)

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

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

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

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

10
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
17
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.5k
points)

6
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
18
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.5k
points)

4
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
19
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.5k
points)

8
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
20
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.5k
points)

7
views
peterlinz
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
proof
0
votes
1
answer
21
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.5k
points)

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

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

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

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

15
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
26
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
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

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

12
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
2
answers
28
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
Mar 16
in
Computer Networks
by
Rishi yadav
Boss
(
10.5k
points)

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

7
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
+1
vote
1
answer
30
Peter Linz Edition 5 Exercise 11.1 Question 10 (Page No. 284)
Is the family of recursive languages closed under concatenation$?$
asked
Mar 16
in
Computer Networks
by
Rishi yadav
Boss
(
10.5k
points)

19
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
My Journey To iiiTH Mtech Cse 2019
IIIT H INTERVIEW EXPERIENCE 2019
IIITH Interview Experience
Thanks GO!!
IIIT Hyerabad Interview Expeience  MS by Research in CSE
Follow @csegate
Recent questions tagged recursiveandrecursivelyenumerablelanguages
Recent Blog Comments
My rank in gate was a disaster...2111 rank and...
Sir whats you rank ?
Ok,Thank you for replying!
By a good profile I mean having academic...
Thank you sir..
49,532
questions
54,134
answers
187,337
comments
71,058
users