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
0
votes
0
answers
511
Peter Linz Edition 5 Exercise 12.1 Question 15 (Page No. 308)
Let $\Gamma = \{0,1,\square\}$ and let $b(n)$ be the maximum number of tape cells examined by any $n-$state Turing machine that halts when started with a blank tape. Show that $b(n)$ is not computable.
Rishi yadav
asked
in
Theory of Computation
Mar 14, 2019
by
Rishi yadav
144
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
0
answers
512
Peter Linz Edition 5 Exercise 12.1 Question 14 (Page No. 308)
Consider the set of all $n-$state Turing machines with tape alphabet $\Gamma = \{0,1,\square\}$. Give an expression for $m(n)$, the number of distinct Turing machines with this $\Gamma$.
Rishi yadav
asked
in
Theory of Computation
Mar 14, 2019
by
Rishi yadav
151
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
1
vote
1
answer
513
Peter Linz Edition 5 Exercise 12.1 Question 13 (Page No. 308)
Let $B$ be the set of all Turing machines that halt when started with a blank tape. Show that this set is recursively enumerable, but not recursive.
Rishi yadav
asked
in
Theory of Computation
Mar 14, 2019
by
Rishi yadav
360
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
0
answers
514
Peter Linz Edition 5 Exercise 12.1 Question 12 (Page No. 308)
Show that the problem of determining whether a Turing machine halts on any input is undecidable.
Rishi yadav
asked
in
Theory of Computation
Mar 14, 2019
by
Rishi yadav
135
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
0
answers
515
Peter Linz Edition 5 Exercise 12.1 Question 11 (Page No. 308)
Let $\Gamma = \{0,1,\square\}$. Consider the function $f(n)$ whose value is the maximum number of moves that can be made by any $n-state$ Turing machine that halts when started with a blank tape. This function, as it turns out, is not computable. Give the values of $f(1)$ and $f(2)$.
Rishi yadav
asked
in
Theory of Computation
Mar 14, 2019
by
Rishi yadav
144
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
0
votes
0
answers
516
Peter Linz Edition 5 Exercise 12.1 Question 10 (Page No. 308)
Let $M$ be any Turing machine and $x$ and $y$ two possible instantaneous descriptions of it. Show that the problem of determining whether or not $x \vdash^{*}_M y$ is undecidable.
Rishi yadav
asked
in
Theory of Computation
Mar 14, 2019
by
Rishi yadav
199
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
1
answer
517
Peter Linz Edition 5 Exercise 12.1 Question 9 (Page No. 308)
$\text{Definition:}\space$A pushdown automaton $M = (Q,\Sigma,\Gamma,\delta,q_0,z,F)$ ... that is, given a pda as in Definition, can we always predict whether or not the automaton will halt on input $w?$
Rishi yadav
asked
in
Theory of Computation
Mar 14, 2019
by
Rishi yadav
316
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
0
answers
518
Peter Linz Edition 5 Exercise 12.1 Question 7,8 (Page No. 308)
$i)$ Show that there is no algorithm for deciding if any two Turing machines $M_1$ and $M_2$ accept the same language. $ii)$ How is the conclusion of $i$ affected if $M_2$ is a finite automaton$?$
Rishi yadav
asked
in
Theory of Computation
Mar 14, 2019
by
Rishi yadav
151
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
1
answer
519
Peter Linz Edition 5 Exercise 12.1 Question 6 (Page No. 308)
Consider the question: $“$Does a Turing machine in the course of a computation revisit the starting cell $($i.e the cell under the read-write head at the beginning of the computation$)?$”$ Is this a decidable question$?$
Rishi yadav
asked
in
Theory of Computation
Mar 14, 2019
by
Rishi yadav
467
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
0
answers
520
Peter Linz Edition 5 Exercise 12.1 Question 5 (Page No. 307)
Show that there is no problem to decide whether or not an arbitrary Turing machine on all input.
Rishi yadav
asked
in
Theory of Computation
Mar 14, 2019
by
Rishi yadav
161
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
0
answers
521
Peter Linz Edition 5 Exercise 12.1 Question 4 (Page No. 307)
In the general halting problem, we ask for an algorithm that gives the correct answer for any $M$ and $w$. We can relax this generality, for example by looking for an algorithm that works for all $M$ but only a ... that determines whether or not $(M,w)$ halts. Show that even in this restricted setting the problem is undecidable.
Rishi yadav
asked
in
Theory of Computation
Mar 14, 2019
by
Rishi yadav
256
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
0
answers
522
Peter Linz Edition 5 Exercise 12.1 Question 3 (Page No. 307)
Show that the following problem is undecidable. Given any Turing machine $M, a\in \Gamma $ and $w \in \Sigma^{+}$, determine whether or not the symbol $a$ is ever written when $M$ is applied to $w$.
Rishi yadav
asked
in
Theory of Computation
Mar 14, 2019
by
Rishi yadav
131
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
0
answers
523
Peter Linz Edition 5 Exercise 12.1 Question 2 (Page No. 307)
$\text{Definition:}$ Let $w_M$ be a string that describes a Turing machine $M = (Q,\Sigma,\Gamma,\delta,q_0,\square,F)$, and let $w$ be a string in $M'$s alphabet. We will assume that $w_m$ and $w_M$ ... or not. Reexamine the proof of Theorem to show that this difference in the definition does not affect the proof in any significant way.
Rishi yadav
asked
in
Theory of Computation
Mar 14, 2019
by
Rishi yadav
166
views
peter-linz
peter-linz-edition5
decidability
theory-of-computation
proof
0
votes
0
answers
524
Peter Linz Edition 5 Exercise 12.1 Question 1 (Page No. 307)
If the halting problem were decidable, then every recursively enumerable language would be recursive. Consequently, the halting problem is undecidable. Describe in detail how $H$ in given Theorem can be modified to produce $H^{\prime} $.
Rishi yadav
asked
in
Theory of Computation
Mar 14, 2019
by
Rishi yadav
235
views
peter-linz
peter-linz-edition5
decidability
theory-of-computation
0
votes
1
answer
525
Peter Linz Edition 4 Exercise 5.1 Question 13.a (Page No. 134)
L={$a^nb^n | n\geq 0$} please show how $L^2$ is CFL
aditi19
asked
in
Theory of Computation
Mar 1, 2019
by
aditi19
416
views
theory-of-computation
peter-linz
peter-linz-edition4
context-free-language
context-free-grammar
1
vote
1
answer
526
Peter Linz Edition 4 Exercise 4.3 Question 6 (Page No. 122)
Given $L_1=${$a^nb^n$|$n\geqslant 1$} , $L_2=${$a^nb^m|n\geq 1, m\geq 1$}, $L_3=${$a^nb^{n+2}|n\geqslant 1$} if $L_1 \cup L_2$ is regular then why $L_1 \cup L_3$ is not regular? also what is the language of $L_1 \cup L_3$?
aditi19
asked
in
Theory of Computation
Feb 25, 2019
by
aditi19
974
views
theory-of-computation
peter-linz
peter-linz-edition4
regular-language
pumping-lemma
2
votes
1
answer
527
Peter Linz Edition 4 Exercise 3.1 Question 5 (Page No. 75)
what is the regular grammar for L={$a^nb^m$ | n+m is even}
aditi19
asked
in
Theory of Computation
Feb 24, 2019
by
aditi19
942
views
theory-of-computation
peter-linz
peter-linz-edition4
finite-automata
regular-language
regular-expression
regular-grammar
1
vote
0
answers
528
Peter Linz Edition 4 Exercise 3.3 Question 6 (Page No. 97)
Construct a right linear grammar for the language $L((aab^*ab)^*)$ is this grammar correct? S->aaA | ε A->bA | abA | S
aditi19
asked
in
Theory of Computation
Feb 24, 2019
by
aditi19
526
views
theory-of-computation
peter-linz
peter-linz-edition4
finite-automata
regular-language
regular-grammar
2
votes
2
answers
529
Peter Linz Edition 4 Exercise 3.2 Question 10.b (Page No. 88)
What is the regular expression for this
aditi19
asked
in
Theory of Computation
Feb 22, 2019
by
aditi19
929
views
theory-of-computation
peter-linz
peter-linz-edition4
finite-automata
regular-language
regular-expression
0
votes
0
answers
530
Self doubt
Do outputs from Mealy and Moore machines get printed only when a transition is made or are lambda transitions allowed? Putting in a different way, what will be the output if empty string is given to the machines? I have read various answers from various sources. It will be helpful if the answer has some source, any answer is welcome.
subho16
asked
in
Theory of Computation
Dec 21, 2018
by
subho16
636
views
theory-of-computation
peter-linz
mealy-machine
moore-machine
0
votes
0
answers
531
Peter Linz Edition 4 Figure 2.10 Example 2.9 (Page No. 52)
PETER LINZ For an nfa, the extended transition function is defined so that ∂*(qi,w) contains qj if and only if there is a walk in the transition graph from qi to qj labeled w. This holds for all qi, qj ∈ Q and w∈S
jatin khachane 1
asked
in
Theory of Computation
Oct 7, 2018
by
jatin khachane 1
469
views
theory-of-computation
peter-linz
peter-linz-edition4
finite-automata
0
votes
2
answers
532
Peter Linz Edition 4 Exercise 3.1 Question 18 (Page No. 76)
Find regular expressions for the following languages on {a, b}. (a) L = {w : |w| mod 3 = 0} (b) L = {w : na (w)mod 3 = 0} (c) L = {w : na (w)mod 5 > 0} Also Design DFA for the same.
Karan Dodwani 1
asked
in
Theory of Computation
Sep 27, 2018
by
Karan Dodwani 1
2.0k
views
regular-language
regular-expression
peter-linz
peter-linz-edition4
0
votes
0
answers
533
Peter Linz Edition 4 Exercise 1.2 Question 14 (Page No. 28)
sky3691841
asked
in
Theory of Computation
Sep 26, 2018
by
sky3691841
407
views
theory-of-computation
peter-linz
peter-linz-edition4
grammar
0
votes
0
answers
534
Peter Linz Edition 4 Exercise 12.1 Question 14 (Page No. 306)
Consider the set of all n-state Turing machines with tape alphabet Γ = {0,1, B}. Give an expression for m(n), the number of distinct Turing machines with this Γ.
RohitKumarSingh
asked
in
Theory of Computation
Sep 19, 2018
by
RohitKumarSingh
223
views
turing-machine
theory-of-computation
peter-linz
peter-linz-edition4
1
vote
0
answers
535
Peter Linz Edition 4 Exercise 2.3 Question 15 (Page No. 63)
From a language $L$ we create a new language $chop2 (L)$ by removing the two leftmost symbols of every string in $L$. Specifically, $chop2(L) =$ {$w: vw ∈ L,$ with $|v|= 2$}. Show that if $L$ is regular, then $chop2 (L)$ is also regular.
vaibhav singh 3
asked
in
Theory of Computation
Sep 14, 2018
by
vaibhav singh 3
612
views
theory-of-computation
peter-linz
peter-linz-edition4
finite-automata
regular-language
0
votes
0
answers
536
Peter Linz Edition 4 Theorem 12.1 (Page No. 301)
How $H'$ ending with initial state $q_{0}$? Plz explain with the figure given
srestha
asked
in
Theory of Computation
Sep 13, 2018
by
srestha
187
views
theory-of-computation
peter-linz
peter-linz-edition4
turing-machine
self-doubt
0
votes
0
answers
537
Peter Linz Edition 4 Theorem 12.1 (Page No. 300)
Need some explanation on these two states. How from first state we can go to the last state as shown the symbol?
srestha
asked
in
Theory of Computation
Sep 13, 2018
by
srestha
254
views
theory-of-computation
peter-linz
peter-linz-edition4
turing-machine
self-doubt
0
votes
0
answers
538
peter linz
The language L1={a^n b^n} union {b} The language L2={a^n b^n} union {a} They both are deterministic CFL. Am i right?
sushmita
asked
in
Theory of Computation
Sep 9, 2018
by
sushmita
503
views
theory-of-computation
peter-linz
context-free-language
0
votes
0
answers
539
Existence of a 2 state NPDA
How can we convert an arbitrary NPDA into an NPDA with at most 2 states? I know the existence of a 3 state PDA, but how can it be done by using just 2 states?
Lakshay Kakkar
asked
in
Theory of Computation
Jul 15, 2018
by
Lakshay Kakkar
227
views
peter-linz
theory-of-computation
npda
2
votes
1
answer
540
Peter Linz Edition 4 (Page No. 51)
Please Explain This:-
swpril
asked
in
Theory of Computation
Jul 9, 2018
by
swpril
650
views
theory-of-computation
finite-automata
peter-linz
peter-linz-edition4
Page:
« prev
1
...
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:...