# 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.

679 questions
Filter by
Sorted by
Tagged with
1 vote
72 views

### Union of non regular and regular language

So I have a regular language L and a non-regular language L' and i want to proof wether the union of both is regular or not. Since I found counterexamples for both cases I want to look at more ...
39 views

### Union of non-regular and finite language

So i got this problem where should prove whether the union of a non regular language $L$ and a finite Language $L'$ is regular or not. My Idea was to show that any regular Language $L_r$ cannot be ...
49 views

### Trying to give a proof about graphs. Having a hard time giving proof for Kruskals algorithm. Can you check my answer?

Question: Let G(V, E) be an undirected connected finite graph with the weight function w : E → R+. Let T be a minimum spanning tree of G. Prove that there exists a run of Kruskal’s algorithm that ...
36 views

### Can proofs by induction be achieved by defining a recursive function between two recursive objects?

I have two types of objects, X and Y, each are recursive structures, and contain different structures sets of tuples containing sets.. etc. The number of elements in X and Y are is the same. I need to ...
27 views

### Confused about decomposition in Context Free Pumping lemma

I am trying to decide whether the following language is context free: $$L = \{ a^nb^{3n}c^n \, | \, n \geq 0 \}$$ Assume $L$ is context-free. Let $p$ be the pumping length given by the Pumping Lemma. ...
18 views

### prove that the language L = { ww | w ∈ {a,b}* } is not context free [duplicate]

I came across this question presented in a past exam. I can see why the language is not context free (you can't know what the first w is, hence you are not able to duplicate it, I hope it makes sense),...
196 views

### Proving the correctness of a greedy algorithm for the Circular Scheduling Problem

Consider the following variation on the Interval Scheduling Problem You have a processor that can operate 24 hours a day, every day. People submit requests to run daily jobs on the processor. Each ...
66 views

### PSPACE≠co-NP?Is the statement true?

Is the statement in question true? how can i prove it formally? I know that PSPACE=CO-PSPACE and NP ⊆ PSPACE and CO-NP ⊆ CO-PSPACE
1 vote
49 views

### Greedy algorithms criterion/ intution

Can anyone please explain (not just through examples) that why does the greedy approach does not work in this case? Or more generally, is there any particular condition under which only the greedy ...
6k views

### False proofs that look correct

I remember seeing a list of False Proofs when I was taking Discrete Maths and I found it to be very interesting and also helpful. So, if anyone knows some common proof mistakes students make or some ...
19 views

### What would be the logical requirements on a language, in order to do direct meta-programming in it?

I am motivated by the idea of generating “words” or “pairs” in a programming language or set of commands. For example, consider any arbitrary REST API. Beyond requesting the original URL endpoint, ...
1 vote
42 views

28 views

### If string x is conjugate to string y, how can you prove that the reverse of x is conjugate to the reverse of y?

I am relatively new to writing proofs and I am stuck trying to prove that if $x$ ~ $y$, then $x^R$ ~ $y^R$. Any help would be appreciated!
1 vote
225 views

### Subtraction on Big Theta notation

This is a question I got for an assignment, and I have been stuck on it for the past few days. Prove that $\Theta(n)+\Theta(n-1) = \Theta(n)$ Does it follow that $\Theta(n) = \Theta(n)-\Theta(n-1)$ I ...
103 views

### Prove there is an algorithm that needs at most n-1 comparisons to check if n-element array has all equal elements?

Question: Prove that there exists an algorithm that can decide using at most n-1 comparisons whether a n-element array contains only equal numbers. We use an algorithm that loops through all the ...
197 views

### What is the contradiction of statement "if $n^2$ is odd then n is odd"

In my opinion the contradiction should be-: If $n^2$ is even then n is even. But it is written in my discrete mathematics book that, "n is even then $n^2$ is odd". How do we find ...
1 vote
33 views

### What do we conclude from diagonalization principle?

I understand $R_{fa}$ etc. I understand why the diagonals are higlighted. I understand D={a,d,f}. But I don't understand what is the conclusion we derive from this?
1 vote
27 views

### Karatsube-Ofman runtime complexity computation

I have a question and didn't understand the solution, since we didn't take how to do it in the lecture and it's not explained in the solution sample. Question: One can generalize the Karatsube-Ofman ...