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
Materials:
Decidability Problems for Grammars
Some Reduction Inferences
Example reductions
Recent questions tagged decidability
0
votes
0
answers
91
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.
admin
asked
in
Theory of Computation
Oct 15, 2019
by
admin
191
views
michael-sipser
theory-of-computation
turing-machine
context-free-grammar
decidability
proof
0
votes
0
answers
92
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.
admin
asked
in
Theory of Computation
Oct 15, 2019
by
admin
214
views
michael-sipser
theory-of-computation
turing-machine
finite-automata
decidability
proof
0
votes
0
answers
93
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.
admin
asked
in
Theory of Computation
Oct 15, 2019
by
admin
502
views
michael-sipser
theory-of-computation
finite-automata
regular-expression
decidability
proof
0
votes
0
answers
94
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.
admin
asked
in
Theory of Computation
Oct 15, 2019
by
admin
206
views
michael-sipser
theory-of-computation
turing-machine
decidability
descriptive
0
votes
0
answers
95
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.
admin
asked
in
Theory of Computation
Oct 15, 2019
by
admin
129
views
michael-sipser
theory-of-computation
decidability
proof
0
votes
0
answers
96
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.
admin
asked
in
Theory of Computation
Oct 15, 2019
by
admin
126
views
michael-sipser
theory-of-computation
turing-machine
decidability
0
votes
0
answers
97
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$ ... $(M,w)$ such that $TM \ M$, started with input $w$, never scans any tape cell more than once.
admin
asked
in
Theory of Computation
Jul 21, 2019
by
admin
170
views
ullman
theory-of-computation
turing-machine
decidability
descriptive
0
votes
1
answer
98
Self Doubt: Decidability
$L=\left \{\langle M_{1},M_{2}\rangle \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 )$
ajaysoni1924
asked
in
Theory of Computation
Jul 15, 2019
by
ajaysoni1924
842
views
theory-of-computation
turing-machine
decidability
recursive-and-recursively-enumerable-languages
4
votes
1
answer
99
UGC NET CSE | June 2019 | Part 2 | Question: 79
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 ... $\omega$ using at most $2^{\mid \omega \mid}$ cells of tape i and ii only i only i, ii and iii iii only
Arjun
asked
in
Theory of Computation
Jul 2, 2019
by
Arjun
2.7k
views
ugcnetcse-june2019-paper2
decidability
turing-machine
0
votes
0
answers
100
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 two-tape deterministic Turing machine, $\text(c)$ on a single-tape nondeterministic Turing machine, $\text(d)$ on a two-tape nondeterministic Turing machine.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
137
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
0
answers
101
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 two-tape deterministic Turing machine, $\text(c)$ on a single-tape nondeterministic Turing machine, $\text(d)$ on a two-tape nondeterministic Turing machine.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
187
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
1
answer
102
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 context-free, $\text(c)$ when $G_2$ is regular$?$
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
294
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
difficult
0
votes
1
answer
103
Peter Linz Edition 5 Exercise 12.4 Question 7 (Page No. 321)
Let $G_1$ be a context-free grammar and $G_2$ a regular grammar. Is the problem $L(G_1)\cap L(G_2) = \phi$ decidable$?$
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
305
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
difficult
0
votes
0
answers
104
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 context-free grammars G.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
202
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
difficult
0
votes
1
answer
105
Peter Linz Edition 5 Exercise 12.4 Question 5 (Page No. 321)
Let $L_1$ be a regular language and $G$ a context-free grammar. Show that the problem $“L_1 \subseteq L(G)”$ is undecidable.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
227
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
difficult
0
votes
0
answers
106
Peter Linz Edition 5 Exercise 12.4 Question 4 (Page No. 321)
$\text{Theorem}:$ There exist no algorithms for deciding whether any given context-free 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 context-free $G$.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
155
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
difficult
0
votes
0
answers
107
Peter Linz Edition 5 Exercise 12.4 Question 3 (Page No. 321)
Show that for arbitrary context-free grammars $G_1$ and $G_2$, the problem $”L(G_1) \space\cap L(G_2) $ is context-free$”$ is undecidable.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
152
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
difficult
0
votes
0
answers
108
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 context-free grammars $G_1,\space G_2$.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
135
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
difficult
0
votes
0
answers
109
Peter Linz Edition 5 Exercise 12.4 Question 1 (Page No. 320)
$\text{Theorem}:$ There exists no algorithm for deciding whether any given context-free grammar is ambiguous. Prove the claim made in Theorem that $G_A$ and $G_B$ by themselves are unambiguous
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
154
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
0
answers
110
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.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
334
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
0
answers
111
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$.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
297
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
0
answers
112
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$?$
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
386
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
0
answers
113
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 single-letter alphabet.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
204
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
0
answers
114
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.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
156
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
0
answers
115
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$?$
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
231
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
0
answers
116
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.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
200
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
0
answers
117
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.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
176
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
0
answers
118
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.
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
205
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
0
answers
119
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$?$
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
759
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
0
votes
0
answers
120
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$?$
Rishi yadav
asked
in
Theory of Computation
Mar 16, 2019
by
Rishi yadav
298
views
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
Page:
« prev
1
2
3
4
5
6
7
8
9
...
16
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 decidability
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:...