Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged recursive-and-recursively-enumerable-languages
1
votes
1
answer
61
Self Doubt:Toc
Hirak
369
views
Hirak
asked
Jun 2, 2019
Theory of Computation
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
0
votes
2
answers
62
Self Doubt:Automata
Intersection of Recursive and Recursively Enumerable language is____________________ ?
Intersection of Recursive and Recursively Enumerable language is____________________ ?
Hirak
690
views
Hirak
asked
Jun 2, 2019
Theory of Computation
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.
Find two examples of languages that are deterministic context-free but not linear.
Rishi yadav
136
views
Rishi yadav
asked
Mar 30, 2019
Theory of Computation
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.
Find two examples of languages that are linear but not deterministic context-free.
Rishi yadav
129
views
Rishi yadav
asked
Mar 30, 2019
Theory of Computation
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.
Given examples that demonstrate that all the subset relations depicted in the figure are indeed proper ones.
Rishi yadav
145
views
Rishi yadav
asked
Mar 30, 2019
Theory of Computation
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|\}$.
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
254
views
Rishi yadav
asked
Mar 17, 2019
Theory of Computation
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|$.
$\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
152
views
Rishi yadav
asked
Mar 17, 2019
Theory of Computation
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.
Show that the family of context-sensitive languages is closed under reversal.
Rishi yadav
131
views
Rishi yadav
asked
Mar 17, 2019
Theory of Computation
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.
Show that the family of context-sensitive languages is closed under union.
Rishi yadav
143
views
Rishi yadav
asked
Mar 17, 2019
Theory of Computation
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)\}$.
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
155
views
Rishi yadav
asked
Mar 17, 2019
Theory of Computation
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\}$.
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)}...
Rishi yadav
157
views
Rishi yadav
asked
Mar 17, 2019
Theory of Computation
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.
A grammar $G = (V, T, S, P)$ is called $\text{unrestricted }$ if all the production are of the form ...
Rishi yadav
221
views
Rishi yadav
asked
Mar 17, 2019
Theory of Computation
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$
Every unrestricted grammar there exists an equivalent unrestricted grammar, all of whose productions have the form ...
Rishi yadav
163
views
Rishi yadav
asked
Mar 17, 2019
Theory of Computation
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$
Show that for every unrestricted grammar there exists an equivalent unrestricted grammar, all of whose productions have the form ...
Rishi yadav
140
views
Rishi yadav
asked
Mar 17, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
+
–
1
votes
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.
$\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)^*)$...
Rishi yadav
183
views
Rishi yadav
asked
Mar 17, 2019
Theory of Computation
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.
$\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 Theor...
Rishi yadav
236
views
Rishi yadav
asked
Mar 17, 2019
Theory of Computation
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$
Prove that constructed grammar cannot generate any sentence with $a\space b$ in it. $S\rightar...
Rishi yadav
138
views
Rishi yadav
asked
Mar 17, 2019
Theory of Computation
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.
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...
Rishi yadav
144
views
Rishi yadav
asked
Mar 17, 2019
Theory of Computation
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$?$
What difficulties would arise if we allowed the empty string as the left side of a production in an unrestricted grammar$?$
Rishi yadav
151
views
Rishi yadav
asked
Mar 17, 2019
Theory of Computation
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$?$
What language does the unrestricted grammar $S\rightarrow S_1B,$ ...
Rishi yadav
208
views
Rishi yadav
asked
Mar 17, 2019
Theory of Computation
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.
Show that the set of all irrational numbers is not countable.
Rishi yadav
802
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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$?$
$\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
188
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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.
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 $...
Rishi yadav
181
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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$.
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 $...
Rishi yadav
304
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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
$\text{Theorem}:$ There exists a recursively enumerable language whose complement is not recursively enumerable.Choose a particular encoding for Turing machines, and with...
Rishi yadav
314
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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$?$
If $L$ is recursive, is it necessarily true that $L^+$ is also recursive$?$
Rishi yadav
152
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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.
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
197
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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.
Let $L_1$ be recursive and $L_2$ recursively enumerable. Show that $L_2-L_1$ is necessarily recursively enumerable.
Rishi yadav
300
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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.
Prove that the complement of a context-free language must be recursive.
Rishi yadav
279
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
+
–
1
votes
1
answer
90
Peter Linz Edition 5 Exercise 11.1 Question 10 (Page No. 284)
Is the family of recursive languages closed under concatenation$?$
Is the family of recursive languages closed under concatenation$?$
Rishi yadav
307
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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 »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register