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
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.5k
points)

6
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
2
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.5k
points)

17
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
3
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.5k
points)

14
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
0
answers
4
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.5k
points)

12
views
theoryofcomputation
peterlinz
decidability
proof
difficult
0
votes
0
answers
5
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.5k
points)

11
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
0
answers
6
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.5k
points)

6
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
0
answers
7
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.5k
points)

8
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
0
answers
8
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.5k
points)

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

5
views
peterlinz
theoryofcomputation
decidability
proof
difficult
0
votes
0
answers
10
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.5k
points)

10
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
11
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.5k
points)

13
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
12
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.5k
points)

13
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
13
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.5k
points)

21
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
14
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.5k
points)

23
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
15
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.5k
points)

8
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
16
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.5k
points)

14
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
17
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.5k
points)

7
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
18
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.5k
points)

8
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
19
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.5k
points)

6
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
20
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.5k
points)

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

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

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

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

6
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
25
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.5k
points)

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

13
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
27
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.5k
points)

24
views
peterlinz
theoryofcomputation
decidability
proof
+1
vote
1
answer
28
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.
asked
Mar 15
in
Theory of Computation
by
Rishi yadav
Boss
(
10.5k
points)

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

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

8
views
peterlinz
theoryofcomputation
decidability
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
The day that made me an IIScian :)
Unanswered Previous year GATE/TIFR questions
From being a Failure to getting into IISc  (Rank 888, Score 692)
My interview experience at IITs/IISc
IIT Delhi CSE Mtech interview 14 may
Follow @csegate
Recent questions tagged decidability
Recent Blog Comments
Congratulations 👍 Very nice experience 😊
Congo :) U deserve it :)
Address will be confirmed again before shipping ...
sir by mistake I have given my home address...
Corrected now 👍
49,541
questions
54,071
answers
187,187
comments
70,978
users