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
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
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
Michael Sipser Edition 3 Exercise 4 Question 4 (Page No. 211)
Let $A\varepsilon_{CFG} = \{ \langle{ G }\rangle \mid G\: \text{is a CFG that generates}\: \epsilon \}.$Show that $A\varepsilon_{CFG}$ is decidable.
asked
8 hours
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.9k
points)

2
views
michaelsipser
theoryofcomputation
turingmachine
cfg
decidability
proof
0
votes
0
answers
2
Michael Sipser Edition 3 Exercise 4 Question 3 (Page No. 211)
Let $ALL_{DFA} = \{ \langle{ A }\rangle \mid A \text{ is a DFA and}\: L(A) = \Sigma^{\ast}\}.$ Show that $ALL_{DFA}$ is decidable.
asked
8 hours
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.9k
points)

2
views
michaelsipser
theoryofcomputation
turingmachine
finiteautomata
decidability
proof
0
votes
0
answers
3
Michael Sipser Edition 3 Exercise 4 Question 2 (Page No. 211)
Consider the problem of determining whether a DFA and a regular expression are equivalent. Express this problem as a language and show that it is decidable.
asked
8 hours
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.9k
points)

1
view
michaelsipser
theoryofcomputation
finiteautomata
regularexpressions
decidability
proof
0
votes
0
answers
4
Michael Sipser Edition 3 Exercise 3 Question 22 (Page No. 190)
Let $A$ be the language containing only the single string $s$ ... of this problem, assume that the question of whether life will be found on Mars has an unambiguous $YES$ or $NO$ answer.
asked
8 hours
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.9k
points)

1
view
michaelsipser
theoryofcomputation
turingmachine
decidability
descriptive
0
votes
0
answers
5
Michael Sipser Edition 3 Exercise 3 Question 18 (Page No. 190)
Show that a language is decidable iff some enumerator enumerates the language in the standard string order.
asked
9 hours
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.9k
points)

1
view
michaelsipser
theoryofcomputation
decidability
proof
0
votes
0
answers
6
Michael Sipser Edition 3 Exercise 3 Question 15 (Page No. 189)
Show that the collection of decidable languages is closed under the operation of union. concatenation. star. complementation. intersection.
asked
9 hours
ago
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
50.9k
points)

1
view
michaelsipser
theoryofcomputation
turingmachine
decidability
0
votes
0
answers
7
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
Veteran
(
50.9k
points)

18
views
ullman
theoryofcomputation
turingmachine
decidability
descriptive
0
votes
1
answer
8
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.4k
points)

123
views
theoryofcomputation
turingmachine
decidability
recursiveandrecursivelyenumerablelanguages
+2
votes
1
answer
9
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
(
420k
points)

81
views
ugcnetjune2019ii
decidability
turingmachine
0
votes
0
answers
10
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
(
11.2k
points)

19
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
11
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
(
11.2k
points)

22
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
1
answer
12
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
(
11.2k
points)

41
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
1
answer
13
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
(
11.2k
points)

31
views
theoryofcomputation
peterlinz
decidability
proof
difficult
0
votes
0
answers
14
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
(
11.2k
points)

15
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
1
answer
15
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
(
11.2k
points)

14
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
0
answers
16
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
(
11.2k
points)

16
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
0
answers
17
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
(
11.2k
points)

9
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
0
answers
18
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
(
11.2k
points)

7
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
0
answers
19
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
(
11.2k
points)

12
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
20
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
(
11.2k
points)

19
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
21
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
(
11.2k
points)

17
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
22
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
(
11.2k
points)

26
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
23
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
(
11.2k
points)

26
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
24
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
(
11.2k
points)

9
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
25
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
(
11.2k
points)

26
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
26
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
(
11.2k
points)

10
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
27
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
(
11.2k
points)

10
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
28
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
(
11.2k
points)

9
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
29
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
(
11.2k
points)

7
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
30
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
(
11.2k
points)

10
views
peterlinz
theoryofcomputation
decidability
proof
Page:
1
2
3
4
5
6
...
13
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
Recruitment to the post of Scientist/Engineer 'SC' (Electronics, Mechanical and Computer Science)
Standard Videos for Calculus
Standard Videos for Linear Algebra
Standard Videos for Graph Theory
Standard Videos for Combinatory
Follow @csegate
Recent questions tagged decidability
Recent Blog Comments
Exam date is 1212020.
Where is this mentioned?
Nope :(
is it for final year student or not??
12Jan2020 exam date
50,309
questions
55,731
answers
192,186
comments
90,359
users