Register

Recent questions tagged proof

0 0 votes
1 1 answer
276
276 views
ISI2025-MCS-PCB (CS) | Question: 2
Let $b_{n} b_{n-1} \cdots b_{1}$ be the decimal representation of an $n$ digit number $m$. Let $b_{n} b_{n-1} \ldots b_{2}$ be the integer $a$ obtained from $m$ by stripp...
User Avatar
1 1 vote
3 answers 3 answers
564
564 views
Proof of Correctness of Different Sorting Algorithms
State Proof of Correctness for Different Popular Sorting AlgorithmSorting AlgoBest Case TCAVg Case TCWorst Case TCStable Sorting?Inplace Sorting?1. Bubble Sort \[O(n) \]\...
User Avatar
0 0 votes
0 0 answers
277
277 views
ISI2024-MCS-PCB (Math) | Question: 8
For any undirected connected graph $G$, let $\chi(G)$ be the minimum number of colours needed to colour all the vertices of $G$ in such a way that no two adjacent vertice...
User Avatar
0 0 votes
0 0 answers
385
385 views
Kenneth Rosen Edition 7 Exercise 8.2 Question 10 (Page No. 525)
Prove Theorem $2:$ Let $c_{1}$ and $c_{2}$ be real numbers with $c_{2}\neq 0.$ Suppose that $r^{2}-c_{1}r-c_{2} = 0$ has only one root $r_{0}.$ A sequence $\{a_{n}\}$ is ...
User Avatar
0 0 votes
0 0 answers
659
659 views
Kenneth Rosen Edition 7 Exercise 6.5 Question 63 (Page No. 434)
Prove the Multinomial Theorem: If $n$ is a positive integer, then $\displaystyle{}(x_{1} + x_{2} + \dots + x_{m})^{n} = \sum_{n_{1} + n_{2} + \dots + n_{m} = n}\:\: C(n:n...
User Avatar
0 0 votes
0 0 answers
312
312 views
Kenneth Rosen Edition 7 Exercise 6.4 Question 32 (Page No. 422)
Prove the binomial theorem using mathematical induction.
User Avatar
3 3 votes
0 0 answers
869
869 views
Michael Sipser Edition 3 Exercise 5 Question 36 (Page No. 242)
Say that a $CFG$ is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{CFG} = \{\langle G \rangle \mid \text{G is a minimal CF...
User Avatar
1 1 vote
0 0 answers
521
521 views
Michael Sipser Edition 3 Exercise 5 Question 35 (Page No. 242)
Say that a variable $A$ in $CFG \:G$ is necessary if it appears in every derivation of some string $w \in G$. Let $NECESSARY_{CFG} = \{\langle G, A\rangle \mid \text{A is...
User Avatar
0 0 votes
1 1 answer
1.2k
1.2k views
Michael Sipser Edition 3 Exercise 5 Question 34 (Page No. 241)
Let $X = \{\langle M, w \rangle \mid \text{M is a single-tape TM that never modifies the portion of the tape that contains the input $w$ } \}$Is $X$ decidable? Prove you...
User Avatar
1 1 vote
2 2 answers
1.1k
1.1k views
Michael Sipser Edition 3 Exercise 5 Question 33 (Page No. 241)
Consider the problem of determining whether a $PDA$ accepts some string of the form $\{ww \mid w \in \{0,1\}^{\ast} \}$ . Use the computation history method to show that ...
User Avatar
0 0 votes
0 0 answers
638
638 views
Michael Sipser Edition 3 Exercise 5 Question 32 (Page No. 241)
Prove that the following two languages are undecidable.$OVERLAP_{CFG} = \{\langle G, H\rangle \mid \text{G and H are CFGs where}\: L(G) \cap L(H) \neq \emptyset\}$.$PREF...
User Avatar
0 0 votes
0 0 answers
569
569 views
Michael Sipser Edition 3 Exercise 5 Question 31 (Page No. 241)
Let$f(x)=\left\{\begin{matrix}3x+1 & \text{for odd}\: x& \\ \dfrac{x}{2} & \text{for even}\: x & \end{matrix}\right.$for any natural number $x$. If you start with an inte...
User Avatar
1 1 vote
0 0 answers
563
563 views
Michael Sipser Edition 3 Exercise 5 Question 30 (Page No. 241)
Use Rice’s theorem, to prove the undecidability of each of the following languages.$INFINITE_{TM} = \{\langle M \rangle \mid \text{M is a TM and L(M) is an infinite langu...
User Avatar
0 0 votes
0 0 answers
730
730 views
Michael Sipser Edition 3 Exercise 5 Question 29 (Page No. 241)
Rice’s theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine’s language ha...
User Avatar
0 0 votes
0 0 answers
576
576 views
Michael Sipser Edition 3 Exercise 5 Question 28 (Page No. 241)
Rice’s theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine’s language ha...
User Avatar
1 1 vote
0 0 answers
682
682 views
Michael Sipser Edition 3 Exercise 5 Question 27 (Page No. 241)
A two-dimensional finite automaton $(2DIM-DFA)$ is defined as follows. The input is an $m \times n$ rectangle, for any $m, n \geq 2$. The squares along the boundary of th...
User Avatar
0 0 votes
0 0 answers
576
576 views
Michael Sipser Edition 3 Exercise 5 Question 26 (Page No. 240)
Define a two-headed finite automaton $(2DFA)$ to be a deterministic finite automaton that has two read-only, bidirectional heads that start at the left-hand end of the in...
User Avatar
0 0 votes
0 0 answers
518
518 views
Michael Sipser Edition 3 Exercise 5 Question 25 (Page No. 240)
Give an example of an undecidable language $B$, where $B \leq_{m} \overline{B}$.
User Avatar
0 0 votes
0 0 answers
375
375 views
Michael Sipser Edition 3 Exercise 5 Question 24 (Page No. 240)
Let $J = \{w \mid \text{either $w = 0x$ for some $x \in A_{TM},$ or $w = 1y\:$ for some $y \in \overline{A_{TM}}\:\:$}\}$. Show that neither $J$ nor $\overline{J}$ is Tur...
User Avatar
0 0 votes
1 1 answer
440
440 views
Michael Sipser Edition 3 Exercise 5 Question 23 (Page No. 240)
Show that $A$ is decidable iff $A \leq_{m} 0 ^{\ast} 1^{\ast}$ .
User Avatar
0 0 votes
0 0 answers
372
372 views
Michael Sipser Edition 3 Exercise 5 Question 22 (Page No. 240)
Show that $A$ is Turing-recognizable iff $A \leq_{m} A_{TM}$.
User Avatar
0 0 votes
0 0 answers
560
560 views
Michael Sipser Edition 3 Exercise 5 Question 21 (Page No. 240)
Let $AMBIG_{CFG} = \{\langle G \rangle \mid \text{G is an ambiguous CFG}\}$. Show that $AMBIG_{CFG}$ is undecidable. (Hint: Use a reduction from $PCP$. Given an instance...
User Avatar
0 0 votes
0 0 answers
469
469 views
Michael Sipser Edition 3 Exercise 5 Question 20 (Page No. 240)
Prove that there exists an undecidable subset of $\{1\}^{\ast}$ .
User Avatar
0 0 votes
0 0 answers
526
526 views
Michael Sipser Edition 3 Exercise 5 Question 19 (Page No. 240)
In the silly Post Correspondence Problem, $SPCP$, the top string in each pair has the same length as the bottom string. Show that the $SPCP$ is decidable.
User Avatar
0 0 votes
0 0 answers
648
648 views
Michael Sipser Edition 3 Exercise 5 Question 18 (Page No. 240)
Show that the Post Correspondence Problem is undecidable over the binary alphabet $\Sigma = \{0,1\}$.
User Avatar
0 0 votes
0 0 answers
432
432 views
Michael Sipser Edition 3 Exercise 5 Question 17 (Page No. 240)
Show that the Post Correspondence Problem is decidable over the unary alphabet $\Sigma = \{1\}$.
User Avatar
0 0 votes
0 0 answers
615
615 views
Michael Sipser Edition 3 Exercise 5 Question 16 (Page No. 240)
Let $\Gamma = \{0, 1, \sqcup\}$ be the tape alphabet for all TMs in this problem. Define the busy beaver function $BB: N \rightarrow N$ as follows. For each value of $k$,...
User Avatar
1 1 vote
0 0 answers
2.8k
2.8k views
Michael Sipser Edition 3 Exercise 5 Question 15 (Page No. 240)
Consider the problem of determining whether a Turing machine $M$ on an input w ever attempts to move its head left at any point during its computation on $w$. Formulate t...
User Avatar
0 0 votes
0 0 answers
473
473 views
Michael Sipser Edition 3 Exercise 5 Question 14 (Page No. 240)
Consider the problem of determining whether a Turing machine $M$ on an input $w$ ever attempts to move its head left when its head is on the left-most tape cell. Formulat...
User Avatar
0 0 votes
0 0 answers
534
534 views
Michael Sipser Edition 3 Exercise 5 Question 13 (Page No. 239)
A useless state in a Turing machine is one that is never entered on any input string. Consider the problem of determining whether a Turing machine has any useless states....
User Avatar
Page: