Register

Recent questions tagged proof

0 0 votes
1 1 answer
292
292 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
597
597 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
281
281 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
394
394 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
673
673 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
331
331 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
877
877 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
531
531 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
646
646 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
578
578 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
573
573 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
748
748 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
593
593 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
695
695 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
592
592 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
532
532 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
385
385 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
466
466 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
391
391 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
573
573 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
482
482 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
537
537 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
653
653 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
439
439 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
623
623 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
3.0k
3.0k 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
486
486 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
547
547 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: