Register

Materials:

Recent questions tagged decidability

0 0 votes
0 0 answers
403
403 views
Michael Sipser Edition 3 Exercise 4 Question 29 (Page No. 212)
Let $C_{CFG} = \{\langle G, k \rangle \mid \text{ G is a CFG and L(G) contains exactly $k$ strings where $k \geq 0$ or $k = \infty$}\}$. Show that $C_{CFG}$ is decidable...
User Avatar
0 0 votes
0 0 answers
293
293 views
Michael Sipser Edition 3 Exercise 4 Question 28 (Page No. 212)
Let $C = \{ \langle G, x \rangle \mid \text{G is a CFG $x$ is a substring of some $y \in L(G)$}\}$. Show that $C$ is decidable. (Hint: An elegant solution to this problem...
User Avatar
0 0 votes
0 0 answers
389
389 views
Michael Sipser Edition 3 Exercise 4 Question 27 (Page No. 212)
Let $E = \{\langle M \rangle \mid \text{ M is a DFA that accepts some string with more 1s than 0s}\}$. Show that $E$ is decidable. (Hint: Theorems about $CFLs$ are helpfu...
User Avatar
0 0 votes
1 1 answer
515
515 views
Michael Sipser Edition 3 Exercise 4 Question 26 (Page No. 212)
Let $PAL_{DFA} = \{ \langle M \rangle \mid \text{ M is a DFA that accepts some palindrome}\}$. Show that $PAL_{DFA}$ is decidable. (Hint: Theorems about $CFLs$ are helpfu...
User Avatar
0 0 votes
0 0 answers
348
348 views
Michael Sipser Edition 3 Exercise 4 Question 25 (Page No. 212)
Let $BAL_{DFA} = \{ \langle M \rangle \mid \text{ M is a DFA that accepts some string containing an equal number of 0s and 1s}\}$.Show that $BAL_{DFA}$ is decidable. (Hin...
User Avatar
0 0 votes
0 0 answers
751
751 views
Michael Sipser Edition 3 Exercise 4 Question 24 (Page No. 212)
A useless state in a pushdown automaton is never entered on any input string. Consider the problem of determining whether a pushdown automaton has any useless states. For...
User Avatar
0 0 votes
0 0 answers
530
530 views
Michael Sipser Edition 3 Exercise 4 Question 23 (Page No. 212)
Say that an $NFA$ is ambiguous if it accepts some string along two different computation branches. Let $AMBIG_{NFA} = \{ \langle N \rangle \mid \text{ N is an ambiguous N...
User Avatar
0 0 votes
0 0 answers
565
565 views
Michael Sipser Edition 3 Exercise 4 Question 22 (Page No. 212)
Let $PREFIX-FREE_{REX} = \{\langle R \rangle \mid \text{R is a regular expression and L(R) is prefix-free}\}$. Show that $PREFIX FREE_{REX}$ is decidable. Why does a simi...
User Avatar
0 0 votes
0 0 answers
253
253 views
Michael Sipser Edition 3 Exercise 4 Question 21 (Page No. 212)
Let $S = \{\langle M \rangle \mid \text{M is a DFA that accepts}\: \text{ $w^{R}$ whenever it accepts $w$}\}$. Show that $S$ is decidable.
User Avatar
0 0 votes
0 0 answers
248
248 views
Michael Sipser Edition 3 Exercise 4 Question 19 (Page No. 212)
Prove that the class of decidable languages is not closed under homomorphism.
User Avatar
0 0 votes
0 0 answers
305
305 views
Michael Sipser Edition 3 Exercise 4 Question 18 (Page No. 212)
Let $C$ be a language. Prove that $C$ is Turing-recognizable iff a decidable language $D$ exists such that $C = \{x \mid \exists y (\langle{ x, y \rangle} \in D)\}$.
User Avatar
0 0 votes
0 0 answers
397
397 views
Michael Sipser Edition 3 Exercise 4 Question 17 (Page No. 212)
Prove that $EQ_{DFA}$ is decidable by testing the two DFAs on all strings up to a certain size. Calculate a size that works.
User Avatar
0 0 votes
0 0 answers
334
334 views
Michael Sipser Edition 3 Exercise 4 Question 16 (Page No. 212)
Let $A = \{ \langle R \rangle \mid \text{R is a regular expression describing a language containing at least one string w that has 111 as a substring} \text{(i.e., w = x...
User Avatar
0 0 votes
0 0 answers
739
739 views
Michael Sipser Edition 3 Exercise 4 Question 15 (Page No. 212)
Show that the problem of determining whether a CFG generates all strings in $1^{\ast}$ is decidable. In other words, show that $\{\langle { G \rangle} \mid \text{G is a C...
User Avatar
0 0 votes
0 0 answers
344
344 views
Michael Sipser Edition 3 Exercise 4 Question 14 (Page No. 211)
Let $\Sigma = \{0,1\}$. Show that the problem of determining whether a $CFG$ generates some string in $1^{\ast}$ is decidable. In other words, show that $\{\langle {G \ra...
User Avatar
0 0 votes
0 0 answers
253
253 views
Michael Sipser Edition 3 Exercise 4 Question 13 (Page No. 211)
Let $A = \{ \langle{ R, S \rangle} \mid \text{R and S are regular expressions and} \: L(R) \subseteq L(S)\}$. Show that $A$ is decidable.
User Avatar
0 0 votes
0 0 answers
278
278 views
Michael Sipser Edition 3 Exercise 4 Question 12 (Page No. 211)
Let $A = \{\langle{ M \rangle} \mid \text{M is a DFA that doesn’t accept any string containing an odd number of 1s}\}$.Show that $A$ is decidable.
User Avatar
0 0 votes
0 0 answers
336
336 views
Michael Sipser Edition 3 Exercise 4 Question 11 (Page No. 211)
Let $INFINITE_{PDA} = \{\langle{ M \rangle} \mid \text{M is a PDA and L(M) is an infinite language}\}$. Show that $INFINITE_{PDA}$ is decidable.
User Avatar
0 0 votes
0 0 answers
316
316 views
Michael Sipser Edition 3 Exercise 4 Question 10 (Page No. 211)
Let $INFINITE_{DFA} = \{\langle{ A \rangle} \mid \text{ A is a DFA and L(A) is an infinite language}\}$. Show that $INFINITE_{DFA}$ is decidable.
User Avatar
0 0 votes
0 0 answers
265
265 views
Michael Sipser Edition 3 Exercise 4 Question 7 (Page No. 211)
Let $B$ be the set of all infinite sequences over $\{0,1\}$. Show that $B$ is uncountable using a proof by diagonalization.
User Avatar
0 0 votes
0 0 answers
336
336 views
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.
User Avatar
0 0 votes
0 0 answers
373
373 views
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.
User Avatar
0 0 votes
0 0 answers
697
697 views
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.
User Avatar
0 0 votes
0 0 answers
381
381 views
Michael Sipser Edition 3 Exercise 3 Question 22 (Page No. 190)
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...
User Avatar
0 0 votes
0 0 answers
244
244 views
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.
User Avatar
0 0 votes
0 0 answers
266
266 views
Michael Sipser Edition 3 Exercise 3 Question 15 (Page No. 189)
Show that the collection of decidable languages is closed under the operation ofunion.concatenation.star.complementation.intersection.
User Avatar
0 0 votes
0 0 answers
311
311 views
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 t...
User Avatar
0 0 votes
1 1 answer
1.5k
1.5k views
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} \ri...
User Avatar
4 4 votes
1 1 answer
3.5k
3.5k views
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...
User Avatar
Page: