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 peter-linz
1
vote
1
answer
451
Peter Linz Edition 4 Exercise 1.2 Question 1 (Page No. 27)
Use induction on $n$ to show that $|u^n|=n|u|$ for all strings $u$ and all $n$.
Naveen Kumar 3
asked
in
Theory of Computation
Mar 17, 2019
by
Naveen Kumar 3
273
views
peter-linz
peter-linz-edition4
theory-of-computation
proof
0
votes
0
answers
452
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
260
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
453
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
157
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
454
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
138
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
proof
0
votes
0
answers
455
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
148
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
proof
0
votes
0
answers
456
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
160
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
difficult
0
votes
0
answers
457
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
160
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
difficult
0
votes
0
answers
458
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
227
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
459
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
460
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
145
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
1
vote
0
answers
461
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
189
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
462
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
241
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
463
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
141
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
464
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
151
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
465
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
159
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
466
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
215
views
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
proof
0
votes
1
answer
467
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
823
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
468
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
200
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
469
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
185
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
1
answer
470
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
316
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
1
answer
471
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
323
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
1
answer
472
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
473
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
206
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
2
answers
474
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
315
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
1
answer
475
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
289
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
1
vote
1
answer
476
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
314
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
477
Peter Linz Edition 5 Exercise 11.1 Question 9 (Page No. 284)
Show that the families of recursively enumerable and recursive languages are closed under reversal.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
188
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
478
Peter Linz Edition 5 Exercise 11.1 Question 8 (Page No. 284)
Show that the family of recursive languages is closed under union and intersection.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
145
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
1
vote
1
answer
479
Peter Linz Edition 5 Exercise 11.1 Question 7 (Page No. 284)
Is the family of recursively enumerable languages closed under intersection$?$
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
211
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
480
Peter Linz Edition 5 Exercise 11.1 Question 6 (Page No. 284)
Show that the family of recursively enumerable languages is closed under union.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
110
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
Page:
« prev
1
...
11
12
13
14
15
16
17
18
19
20
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 peter-linz
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:...