Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
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.
Let $A\varepsilon_{CFG} = \{ \langle{ G }\rangle \mid G\: \text{is a CFG that generates}\: \epsilon \}.$Show that $A\varepsilon_{CFG}$ is decidable.
admin
188
views
admin
asked
Oct 15, 2019
Theory of Computation
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.
Let $ALL_{DFA} = \{ \langle{ A }\rangle \mid A \text{ is a DFA and}\: L(A) = \Sigma^{\ast}\}.$ Show that $ALL_{DFA}$ is decidable.
admin
210
views
admin
asked
Oct 15, 2019
Theory of Computation
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.
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
501
views
admin
asked
Oct 15, 2019
Theory of Computation
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.
Let $A$ be the language containing only the single string $s$, where$s = \left\{\begin{matrix} \text{0 if life never will be found on Mars} \\ \:\: \text{1 if life will b...
admin
202
views
admin
asked
Oct 15, 2019
Theory of Computation
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.
Show that a language is decidable iff some enumerator enumerates the language in the standard string order.
admin
124
views
admin
asked
Oct 15, 2019
Theory of Computation
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.
Show that the collection of decidable languages is closed under the operation ofunion.concatenation.star.complementation.intersection.
admin
124
views
admin
asked
Oct 15, 2019
Theory of Computation
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.
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 t...
admin
167
views
admin
asked
Jul 21, 2019
Theory of Computation
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 )$
$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} \ri...
ajaysoni1924
823
views
ajaysoni1924
asked
Jul 15, 2019
Theory of Computation
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
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...
Arjun
2.7k
views
Arjun
asked
Jul 2, 2019
Theory of Computation
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.
Consider the language $L = \{www:w\in\{a, b\}^+\}$.Discuss the construction and efficiency of algor...
Rishi yadav
129
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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.
Consider the language $L = \{ww:w\in\{a, b\}^+\}$.Discuss the construction and efficiency of algor...
Rishi yadav
182
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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$?$
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...
Rishi yadav
288
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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$?$
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
294
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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.
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 ...
Rishi yadav
201
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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.
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
217
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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$.
$\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 The...
Rishi yadav
150
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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.
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
148
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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$.
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
133
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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
$\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 thems...
Rishi yadav
153
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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.
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 = ...
Rishi yadav
333
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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$.
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 ...
Rishi yadav
296
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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$?$
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
385
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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.
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}$ solut...
Rishi yadav
200
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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.
$\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 ...
Rishi yadav
152
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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$?$
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
224
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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.
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 ...
Rishi yadav
193
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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.
Let $G_1$ be an unrestricted grammar, and $G_2$ any regular grammar. Show that the problem $L(G_1) \spa...
Rishi yadav
173
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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.
Let $G_1$ be an unrestricted grammar, and $G_2$ any regular grammar. Show that the problem $L(G_1) \space\ca...
Rishi yadav
200
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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$?$
Let $G$ be an unrestricted grammar. Does there exist an algorithm for determining whether or not $L(G) = L(G)^R$$?$
Rishi yadav
759
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
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$?$
Let $G$ be an unrestricted grammar. Does there exist an algorithm for determining whether or not $L(G)^R$ is recursive enumerable$?$
Rishi yadav
294
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
Page:
« prev
1
2
3
4
5
6
7
8
9
...
16
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register