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
All Activity
Questions
Unanswered
Tags
Categories
Users
Ask a Question
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 decidability
Materials:
Decidability Problems for Grammars
Some Reduction Inferences
Example reductions
0
votes
0
answers
1
Ullman (TOC) Edition 3 Exercise 9.3 Question 6 (Page No. 400)
Show that the following questions are decidable: The set of codes for $TM's \ M$ such that when started with blank tape will eventually write some nonblank symbol on its tape. Hint: If $M$ has $m$ states, consider the first $m$ transitions ... $(M,w)$ such that $TM \ M$, started with input $w$, never scans any tape cell more than once.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
45.8k
points)

4
views
ullman
theoryofcomputation
turingmachine
decidability
descriptive
0
votes
1
answer
2
Self Doubt: Decidability
$L=\left \{< M_{1},M_{2}> \text{such that L}(M_{1})\prec L(M_{2}) \right \}$ is it recursive enumerable? here $L\left ( M_{1} \right )\prec L\left ( M_{2} \right )$ signifies language $L\left ( M_{1} \right )$ is reducible to $L\left ( M_{2} \right )$
asked
Jul 15
in
Theory of Computation
by
ajaysoni1924
Boss
(
10.2k
points)

85
views
theoryofcomputation
turingmachine
decidability
recursiveandrecursivelyenumerablelanguages
+2
votes
1
answer
3
UGCNETJune2019II79
Which of the following problems is/are decidable problem(s) (recursively enumerable) on turing machine $M$? $G$ is a CFG with $L(G)=\phi$ There exist two TMs $M_1$ and $M_2$ such that $L(M) \subseteq \{L(M_1) \cup L(M_2)\} = $ language of all TMs. $M$ is a TM that accepts $\omega$ using at most $2^{\mid \omega \mid}$ cells of tape a and b only a only a, b and c c only
asked
Jul 2
in
Theory of Computation
by
Arjun
Veteran
(
416k
points)

38
views
ugcnetjune2019ii
decidability
turingmachine
0
votes
0
answers
4
Peter Linz Edition 5 Exercise 12.5 Question 2 (Page No. 323)
Consider the language $L = \{www:w\in\{a, b\}^+\}$. Discuss the construction and efficiency of algorithms for accepting $L$ on $\text(a)$ a standard Turing machine, $\text(b)$ on a twotape deterministic Turing machine, $\text(c)$ on a singletape nondeterministic Turing machine, $\text(d)$ on a twotape nondeterministic Turing machine.
asked
Mar 16
in
Computer Networks
by
Rishi yadav
Boss
(
10.9k
points)

16
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
5
Peter Linz Edition 5 Exercise 12.5 Question 1 (Page No. 323)
Consider the language $L = \{ww:w\in\{a, b\}^+\}$. Discuss the construction and efficiency of algorithms for accepting $L$ on $\text(a)$ a standard Turing machine, $\text(b)$ on a twotape deterministic Turing machine, $\text(c)$ on a singletape nondeterministic Turing machine, $\text(d)$ on a twotape nondeterministic Turing machine.
asked
Mar 16
in
Computer Networks
by
Rishi yadav
Boss
(
10.9k
points)

21
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
1
answer
6
Peter Linz Edition 5 Exercise 12.4 Question 8 (Page No. 321)
Let $G_1$ and $G_2$ be grammars with $G_1$ regular. Is the problem $L(G_1) = L(G_2)$ decidable when $\text(a)$ $G_2$ is unrestricted, $\text(b)$ when $G_2$ is contextfree, $\text(c)$ when $G_2$ is regular$?$
asked
Mar 16
in
Computer Networks
by
Rishi yadav
Boss
(
10.9k
points)

38
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
1
answer
7
Peter Linz Edition 5 Exercise 12.4 Question 7 (Page No. 321)
Let $G_1$ be a contextfree grammar and $G_2$ a regular grammar. Is the problem $L(G_1)\cap L(G_2) = \phi$ decidable$?$
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.9k
points)

21
views
theoryofcomputation
peterlinz
decidability
proof
difficult
0
votes
0
answers
8
Peter Linz Edition 5 Exercise 12.4 Question 6 (Page No. 321)
Let $M$ be any Turing machine. We can assume without loss of generality that every computation involves an even number of moves. For any such computation $q_0w\vdash x_1\vdash x_2\vdash ...\vdash x_n$, we can then construct the string ... to show that $ L(G) = \Sigma^* $ is undecidable over the domain of all contextfree grammars G.
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.9k
points)

14
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
1
answer
9
Peter Linz Edition 5 Exercise 12.4 Question 5 (Page No. 321)
Let $L_1$ be a regular language and $G$ a contextfree grammar. Show that the problem $“L_1 \subseteq L(G)”$ is undecidable.
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.9k
points)

8
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
0
answers
10
Peter Linz Edition 5 Exercise 12.4 Question 4 (Page No. 321)
$\text{Theorem}:$ There exist no algorithms for deciding whether any given contextfree grammar is ambiguous. Show that if the language $L(G_A)\space \cap L(G_B) $ in Theorem is regular, then it must be empty. Use this to show that the problem $“L(G)$ is regular $”$ is undecidable for contextfree $G$.
asked
Mar 16
in
Computer Networks
by
Rishi yadav
Boss
(
10.9k
points)

15
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
0
answers
11
Peter Linz Edition 5 Exercise 12.4 Question 3 (Page No. 321)
Show that for arbitrary contextfree grammars $G_1$ and $G_2$, the problem $”L(G_1) \space\cap L(G_2) $ is contextfree$”$ is undecidable.
asked
Mar 16
in
Computer Networks
by
Rishi yadav
Boss
(
10.9k
points)

7
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
0
answers
12
Peter Linz Edition 5 Exercise 12.4 Question 2 (Page No. 321)
Show that the problem of determining whether or not $L(G_1) \subseteq L(G_2)$ is undecidable for contextfree grammars $G_1,\space G_2$.
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.9k
points)

5
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
0
answers
13
Peter Linz Edition 5 Exercise 12.4 Question 1 (Page No. 320)
$\text{Theorem}:$ There exists no algorithm for deciding whether any given contextfree grammar is ambiguous. Prove the claim made in Theorem that $G_A$ and $G_B$ by themselves are unambiguous
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.9k
points)

10
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
14
Peter Linz Edition 5 Exercise 12.3 Question 6 (Page No. 318)
The correspondence pair $(A, B)$ is said to have an even PC solution if and only if there exists a nonempty sequence of even integers $i,j,..k$ such that $w_iw_j...w_k = v_iv_j...v_k$. Show that the problem of deciding whether or not an arbitrary pair $(A, B)$ has an even PC solution is undecidable.
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.9k
points)

16
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
15
Peter Linz Edition 5 Exercise 12.3 Question 5 (Page No. 317,318)
Show that the following modifications of the Post correspondence problem are undecidable. $\text(a)$ There is an MPC solution if there is a sequence of integers such that $w_iw_j...w_kw_1 = v_iv_j...v_kv_i$. $\text(b)$ There is an MPC solution if there is a sequence of integers such that $w_1w_2w_iw_j...w_k = v_1v_2v_iv_j...v_k$.
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.9k
points)

16
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
16
Peter Linz Edition 5 Exercise 12.3 Question 4 (Page No. 317)
Suppose we restrict the domain of the Post correspondence problem to include only alphabets with exactly two symbols. Is the resulting correspondence problem decidable$?$
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.9k
points)

24
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
17
Peter Linz Edition 5 Exercise 12.3 Question 3 (Page No. 317)
Show that for $\Sigma = 1$, the Post correspondence problem is decidable, that is, there is an algorithm that can decide whether or not $(A, B)$ has a $\text{PC}$ solution for any given $(A, B)$ on a singleletter alphabet.
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.9k
points)

24
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
18
Peter Linz Edition 5 Exercise 12.3 Question 2 (Page No. 317)
$\text{Theorem}:$ Let $G = (V, T, S, P )$ be an unrestricted grammar, with w any string in $T^+$. Let $(A, B)$ be the correspondence pair constructed from $G$ and $w$ be the process exhibited in Figure. Then the ... string $F$ as $v_1$. The order of the rest of the strings is immaterial. Provide the details of the proof of the Theorem.
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.9k
points)

8
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
19
Peter Linz Edition 5 Exercise 12.3 Question 1 (Page No. 317)
Let $A = \{001, 0011, 11, 101\}$ and $B = \{01, 111, 111, 010\}$. Does the pair $(A, B)$ have a PC solution$?$ Does it have an MPC solution$?$
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.9k
points)

22
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
20
Peter Linz Edition 5 Exercise 12.2 Question 8 (Page No. 311)
For an unrestricted grammar $G$, show that the question $“Is \space L(G) = L(G)^*?”$ is undecidable. Argue $\text(a)$ from Rice’s theorem and $\text(b)$ from first principles.
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.9k
points)

9
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
21
Peter Linz Edition 5 Exercise 12.2 Question 7 (Page No. 311)
Let $G_1$ be an unrestricted grammar, and $G_2$ any regular grammar. Show that the problem $L(G_1) \space\cap L(G_2) = \phi $ is undecidable for any fixed $G_2,$ as long as $L(G_2)$ is not empty.
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.9k
points)

9
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
22
Peter Linz Edition 5 Exercise 12.2 Question 6 (Page No. 311)
Let $G_1$ be an unrestricted grammar, and $G_2$ any regular grammar. Show that the problem $L(G_1) \space\cap L(G_2) = \phi $ is undecidable.
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.9k
points)

7
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
23
Peter Linz Edition 5 Exercise 12.2 Question 5 (Page No. 311)
Let $G$ be an unrestricted grammar. Does there exist an algorithm for determining whether or not $L(G) = L(G)^R$?$
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.9k
points)

5
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
24
Peter Linz Edition 5 Exercise 12.2 Question 4 (Page No. 311)
Let $G$ be an unrestricted grammar. Does there exist an algorithm for determining whether or not $L(G)^R$ is recursive enumerable$?$
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.9k
points)

9
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
25
Peter Linz Edition 5 Exercise 12.2 Question 3 (Page No. 311)
Let $M_1$ and $M_2$ be arbitrary Turing machines. Show that the problem $“L(M_1)\subseteq L(M_2)”$ is undecidable.
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.9k
points)

25
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
26
Peter Linz Edition 5 Exercise 12.2 Question 2 (Page No. 311)
Show that the two problems mentioned at the end of the preceding section, namely $\text(a)$ $L(M)$ contains any string of length five, $\text(b)$ $L(M)$ is regular, are undecidable.
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.9k
points)

5
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
27
Peter Linz Edition 5 Exercise 12.2 Question 1 (Page No. 311)
$\text{Theorem}:$ Let $M$ be any Turing machine. Then the question of whether or not $L(M)$ is finite is undecidable. Show in detail how the machine $\widehat{M}$ in $\text{Theorem}$ is constructed.
asked
Mar 16
in
Theory of Computation
by
Rishi yadav
Boss
(
10.9k
points)

6
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
28
Peter Linz Edition 5 Exercise 12.1 Question 16 (Page No. 308)
Determine whether or not the following statements is true: Any problem whose domain is finite is decidable.
asked
Mar 15
in
Theory of Computation
by
Rishi yadav
Boss
(
10.9k
points)

36
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
29
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.
asked
Mar 15
in
Theory of Computation
by
Rishi yadav
Boss
(
10.9k
points)

13
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
30
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$.
asked
Mar 15
in
Theory of Computation
by
Rishi yadav
Boss
(
10.9k
points)

28
views
peterlinz
theoryofcomputation
decidability
proof
Page:
1
2
3
4
5
6
...
12
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
ISI MTECH CS 2019 INTERVIEW EXPERIENCE
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
Interview Experience at IISc
All subject Gate notes from Standard Books!!
Follow @csegate
Recent questions tagged decidability
Recent Blog Comments
Refund time depends on the payment mode ...
@Arjun Sir , when can i expect my refund in the...
This book is returned you can enable a pay now...
@Pranavcool The book stocks are over and no one...
@Lokesh Thats unfortunate. I have refunded you....
49,830
questions
54,802
answers
189,513
comments
80,759
users