Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions tagged recursive-and-recursively-enumerable-languages
1
vote
1
answer
61
Self Doubt:Toc
Hirak
asked
in
Theory of Computation
Jun 2, 2019
by
Hirak
377
views
theory-of-computation
recursive-and-recursively-enumerable-languages
0
votes
2
answers
62
Self Doubt:Automata
Intersection of Recursive and Recursively Enumerable language is____________________ ?
Hirak
asked
in
Theory of Computation
Jun 2, 2019
by
Hirak
726
views
theory-of-computation
recursive-and-recursively-enumerable-languages
0
votes
0
answers
63
Peter Linz Edition 5 Exercise 11.4 Question 3 (Page No. 298)
Find two examples of languages that are deterministic context-free but not linear.
Rishi yadav
asked
in
Theory of Computation
Mar 30, 2019
by
Rishi yadav
140
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
64
Peter Linz Edition 5 Exercise 11.4 Question 2 (Page No. 298)
Find two examples of languages that are linear but not deterministic context-free.
Rishi yadav
asked
in
Theory of Computation
Mar 30, 2019
by
Rishi yadav
133
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
65
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.
Rishi yadav
asked
in
Theory of Computation
Mar 30, 2019
by
Rishi yadav
149
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
66
Peter Linz Edition 5 Exercise 11.3 Question 6 (Page No. 296)
Without explicitly constructing it, show that there exists a context-sensitive grammar for the language $L=\{www^R: w,u\in\{a,b\}^+,|w|\geq|u|\}$.
Rishi yadav
asked
in
Theory of Computation
Mar 17, 2019
by
Rishi yadav
258
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
67
Peter Linz Edition 5 Exercise 11.3 Question 5 (Page No. 296)
$\text{Theorem}:$ Every context-sensitive language $L$ is recursive. For $m$ in Theorem, give explicit bounds for $m$ as a function of $|w|$ and $|V\cup T|$.
Rishi yadav
asked
in
Theory of Computation
Mar 17, 2019
by
Rishi yadav
155
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
68
Peter Linz Edition 5 Exercise 11.3 Question 4 (Page No. 296)
Show that the family of context-sensitive languages is closed under reversal.
Rishi yadav
asked
in
Theory of Computation
Mar 17, 2019
by
Rishi yadav
135
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
proof
0
votes
0
answers
69
Peter Linz Edition 5 Exercise 11.3 Question 3 (Page No. 296)
Show that the family of context-sensitive languages is closed under union.
Rishi yadav
asked
in
Theory of Computation
Mar 17, 2019
by
Rishi yadav
147
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
proof
0
votes
0
answers
70
Peter Linz Edition 5 Exercise 11.3 Question 2 (Page No. 296)
Find context-sensitive 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)\}$.
Rishi yadav
asked
in
Theory of Computation
Mar 17, 2019
by
Rishi yadav
159
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
difficult
0
votes
0
answers
71
Peter Linz Edition 5 Exercise 11.3 Question 1 (Page No. 296)
Find the context-sensitive grammars for the following languages. $\text{(a)}$ $L=\{a^{n+1}b^nc^{n-1} : 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\}$.
Rishi yadav
asked
in
Theory of Computation
Mar 17, 2019
by
Rishi yadav
159
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
difficult
0
votes
0
answers
72
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.
Rishi yadav
asked
in
Theory of Computation
Mar 17, 2019
by
Rishi yadav
226
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
73
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$
Rishi yadav
asked
in
Theory of Computation
Mar 17, 2019
by
Rishi yadav
167
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
74
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$
Rishi yadav
asked
in
Theory of Computation
Mar 17, 2019
by
Rishi yadav
144
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
1
vote
0
answers
75
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.
Rishi yadav
asked
in
Theory of Computation
Mar 17, 2019
by
Rishi yadav
187
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
76
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.
Rishi yadav
asked
in
Theory of Computation
Mar 17, 2019
by
Rishi yadav
240
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
77
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$
Rishi yadav
asked
in
Theory of Computation
Mar 17, 2019
by
Rishi yadav
140
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
78
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.
Rishi yadav
asked
in
Theory of Computation
Mar 17, 2019
by
Rishi yadav
150
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
79
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$?$
Rishi yadav
asked
in
Theory of Computation
Mar 17, 2019
by
Rishi yadav
158
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
80
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$?$
Rishi yadav
asked
in
Theory of Computation
Mar 17, 2019
by
Rishi yadav
214
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
proof
0
votes
1
answer
81
Peter Linz Edition 5 Exercise 11.1 Question 19 (Page No. 284)
Show that the set of all irrational numbers is not countable.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
817
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
82
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$?$
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
197
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
83
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_2-S_1$ cannot be countable.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
184
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
1
answer
84
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$.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
313
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
1
answer
85
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
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
320
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
1
answer
86
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$?$
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
163
views
theory-of-computation
proof
recursive-and-recursively-enumerable-languages
turing-machine
peter-linz
peter-linz-edition5
0
votes
0
answers
87
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.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
202
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
2
answers
88
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_2-L_1$ is necessarily recursively enumerable.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
314
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
1
answer
89
Peter Linz Edition 5 Exercise 11.1 Question 11 (Page No. 284)
Prove that the complement of a context-free language must be recursive.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
288
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
1
vote
1
answer
90
Peter Linz Edition 5 Exercise 11.1 Question 10 (Page No. 284)
Is the family of recursive languages closed under concatenation$?$
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
313
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
Page:
« prev
1
2
3
4
5
6
7
8
9
next »
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
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
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent questions tagged recursive-and-recursively-enumerable-languages
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...