We’re rewarding the question askers & reputations are being recalculated! Read more.

# Questions tagged [proof-techniques]

Questions about general methods and techniques for proving multiple theorems. When asking about the proof of a single statement, use tags relating to what the proof is about instead.

521 questions
Filter by
Sorted by
Tagged with
66 views

### How do I prove or disprove the following statements? [on hold]

I have to prove or disprove the following statements. a) ≈(L(X)) ⊆ ≈(L(Y)) ⇒ ~(X) ⊆ ~(Y) b) L(X) ⊆ L(Y) ⇒ ~(X) ⊆ ~(Y) ...
24 views

### Why can't non-deterministic pushdown automata always be expressed as deterministic PDAs? [on hold]

Why can't non-deterministic pushdown automata always be expressed as deterministic PDAs?
45 views

### On the complexity of existential and universal quantifiers

I'm trying to analyze the time complexities of the two former kind of quantifiers, I need help figuring out if I'm following the right path or if I'm making mistakes, here's what I've produced so far: ...
39 views

101 views

### Language of CFG: $S \to aS | aSbS | \varepsilon$

I'm trying to prove that the language L generated by the CFG $S \to aS | aSbS | \varepsilon$ is the language $L=\{ w \in \{a,b\}^*: \text{every prefix of$w$has at least as many$a$'s as$b$'s} \}$.I ...
47 views

### Randomly built binary search trees

In Introduction to Algorithms (CLRS) 3rd Edition, page 299, the section attempts to prove: The expected height of a randomly built binary search tree on $n$ distinct keys is $O(\lg n)$. We define "...
101 views

### The law of excluded middle and decidability

I will divide my question in two parts. The first part I am sure that there is a objective answer, but I am not sure about the second part. First part: Is it all (decisions) problems trivial to prove ...
3k views

### Show that there are infinitely more problems than we will ever be able to compute

I was looking at this reading of MIT on computational complexity and on minute 15:00 Erik Demaine embarks on a demonstration to show what is stated in the title of this question. However I cannot ...
40 views

### It is decidable whether a pushdown automaton will accept a word? [duplicate]

I'm asking myself if the problem of decide whether a push down automaton will accept a word is decidable. I would say that you can simulate a push down automaton with a Turing Machine and, if it ...
90 views

### Prove that $T(n) \leq 8n^2$ or find value of $n$ when statement is not true (recurrence relation)

We have a function $T: \mathbb{N}\to\mathbb{N}$ defined recurrently: $$T(n)=\begin{cases} 0 &\text{ if } n=0,\\ 3T(\lfloor{n/2}\rfloor) + 2n^2 &\text{otherwise.} \end{cases}$$ Prove that for ...
101 views

### Could we define the decimal notation of a natural number as a series of operations applied to 0? [closed]

People have made mistakes. For that reason, there probably is a demand by some people for a computer program that's easier to verify makes the calculations properly. I think that according to the ...
9k views

### How to prove that a language is not recursively enumerable

How does one prove that some arbitrary language $L$ is not recursively enumerable? I know I can prove that the language $L$ is recursively enumerable by constructing a Turing machine $M$ that accepts ...
53 views

### How to reduce $\{w \mid |T(M_w)| \geq 42\}$ to the halting problem?

For a string $w$, $M_w$ denotes the Turing machine whose encoding is $w$. I want to reduce the language $L=\{w \mid |T(M_w)| \geq 42\}$ to $H_0 = \{w \mid M_w \text{ halts on } \epsilon\}$, but I ...
37 views

### Proof that this sorting algorithm sorts the input

I'm given this "sorting" algorithm and now I'm supposed to prove, that if given an array of integers of length $n$, sort(A,0,n-1) will sort it. ...
60 views

### How do we prove the time complexity of this simple problem in probabilistic inference on a Bayesian network?

Suppose we have a simple Bayesian network with two rows of nodes: $x_1, x_2, \ldots, x_n$ and $y_1, y_2, \ldots, y_n$. Each node $x_k$ takes a state of either 0 or 1 with equal probability. Each ...
509 views

### Is there a *simple* proof that the intersection of a CFL and a regular language is a CFL?

I am following a course on complexity theory where languages are a part of the course. There is a proof that no matter how hard I try to understand, it is till so complex that I cannot make it to half ...
74 views

### Red-black tree trinode restructuring after insertion and deletion

When performing an insertion/deletion on a red-black tree, how can be argued or proved that it requires at most one/two trinode restructuring(s) respectively? My thoughts so far were: after inserting ...
52 views

### How to correctly describe this action, deleting an edge that “shortcut” some vertices

Haven't written a proof in years, not sure how to describe an algorithm like this ? Let us what we have a graph. like this below: 1). How to describe edge removal of{ (0, 1),(3,4), (1,2) }done in ...
236 views

### Turing machine with semi infinite tape - Prove by construction

I'm studying constrained Turing Machines. There's a theorem that proves that both infinite and semi-infinite tape TM have the same computational power. The theorem that proves this by emulating a TM1 ...
3k views

### How to show two models of computation are equivalent?

I'm seeking explanation on how one could prove that two models of computation are equivalent. I have been reading books on the subject except that equivalence proofs are omitted. I have a basic idea ...
225 views

### prove by induction that the complete recursion tree for computing the nth Fibonacci number has n leaves

I have referenced this similar question: Prove correctness of recursive Fibonacci algorithm, using proof by induction *Edit: my professor had a significant typo in this assignment, I have attempted ...
59 views

33 views

### Finding maximum takes at least $\lceil n/2 \rceil$ comparisons

We are given an array $A$ with $n$ elements, $n \in \mathbb{N}$ and all elements are in the set $\{1,2,3, \cdots, n \}$. I want to prove that finding the maximum in $A$ (that is, outputting the index ...
631 views

### Proof of correctness of algorithm

Can someone help me prove the correctness of this algorithm: ...
130 views

### Union of infinitely many regular languages [duplicate]

I need to prove or disprove the following statement. If $A_n ⊆ \Sigma^*$ is regular for each $n \in \mathbb{N}$ then $\bigcup\limits_{n=0}^{\infty} A_n$ is regular. I know that if two languages ...
97 views

### Proving the singleton language {x} is regular for all x ∈ Σ*

So I'm aware that the singleton language is in fact regular for all x ∈ Σ*, but I do not understand why it is. A formal proof would help, but also getting some intuition as to why it is regular would ...
11k views

### Converting context-free grammar to chomsky normal form

I'm trying to prove that the following CFG can be converted to a CNF: S -> aAB A -> aAa A -> bb B -> a Here below is how I've managed so far: Step 1:...
110 views

### Proving that Every Full Prefix-Free Language is Maximal

I'm practicing a problem where I need to prove that every full prefix-free language is maximal. I know a prefix-free language A is maximal if it is not a proper subset of any prefix-free language, ...