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
1
vote
2
answers
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 ...
- 11
0
votes
0
answers
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 ...
- 11
-1
votes
1
answer
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 ...
- 19
0
votes
2
answers
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 ...
- 165
0
votes
0
answers
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.
...
- 1
0
votes
0
answers
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),...
- 11
0
votes
1
answer
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 ...
0
votes
1
answer
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
1
answer
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 ...
- 113
25
votes
13
answers
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 ...
0
votes
0
answers
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, ...
- 123
1
vote
0
answers
42
views
Is this a correct way of using structural induction to prove type uniqueness?
I was reading the book "Types and Programming Languages" by Benjamin C. Pierce, paying attention to proofs so I could learn proof techniques.
In the parts discussing the simply typed $\...
- 984
1
vote
0
answers
33
views
Random process on ternary string
Given a ternary string S of length N, do the following:
Find the first strictly decreasing pair of digits.
Randomly change one of the digits in the pair to another value.
The string is circular (i.e ...
- 11
0
votes
1
answer
33
views
Proof techniques and correctness proof of minimum cost to make string equal
I've lately been struggling to write correctness proofs for various algorithms, even when it is "obvious" to me that the algorithm works and is correct. For example, take the following ...
- 215
0
votes
0
answers
59
views
Proving that the polish notation has unique readability
I am familiar with the polish notation when it comes to algorithmically reading phrases, but I am having a hard time proving the following exercise:
K is a function so that 1) $K(*)$ is an integer if ...
- 225
0
votes
0
answers
77
views
How to prove (L+M)* = M*.(L.M*)*
Question is to simplify (LM*)* and I couldn't figure out a way to simplify it. Since (L+M)* = M*.(L.M*)*, I guess we can say that it cannot be simplified more. So how do we prove that they are the ...
- 67
0
votes
0
answers
95
views
How to prove the performance ratio of the approximation algorithm of maximum clique is unbounded
Consider the following approximation algorithm for the problem of finding a maximum clique in a given graph $G$. Repeat the following step until the resulting graph is a clique. Delete from $G$ a ...
- 1
0
votes
0
answers
32
views
Show that Language L = { <M> | M is a TM and {b}* ∩ L(M) ≠ ∅ } is recursively enumerable?
I'm not sure how to show that the language L = {M | M is a TM and {b}* ∩ L(M) ≠ ∅ } is recursively enumerable. I understand that if there is a DTM that accepts every word of the given alphabet, it is ...
- 1
1
vote
1
answer
137
views
(Directed) Graphs: Minimal Vertices Subset With No Outgoing Edges
I've been trying to study some graph algorithms and, as part of it, prove a bunch of graph theorems in order to practice my ability to do theoretical work with graphs.
Specifically, I've been trying ...
- 113
0
votes
0
answers
46
views
Proof that Path with admissible edges is shortest
Consider an unweighted and directed graph G(V, E). Suppose, for every vertex v ∈ V we assign a vertex label y(v).
We say that the vertex labeling is valid if for every edge (u, v) ∈ E that is directed ...
0
votes
1
answer
33
views
How can it be formally proved that $f \in O(⌊f ⌋)$
I'm trying to prove that $f \in \mathcal{O}(\lfloor f \rfloor)$ given that $\forall m \in \mathbb{N}, f(m) \geq 1$
Here's what I've thought of so far,
we can set C = 10 and k = 1 and somehow prove ...
0
votes
5
answers
2k
views
Does contradiction definitively prove nonexistence
It is common to have proofs that use contradiction to show that some language is undecidable in computability theory.
An example proof can be seen in 4.2 Undecidability “Introduction to the Theory of ...
0
votes
1
answer
275
views
Proving why decreasing an edge weight in a graph may change it's MST by one edge
I'm working on understanding graphs and graph algorithms.
The problem is from: https://courses.engr.illinois.edu/cs374/fa2020/labs/sol/lab_12_b_sol.pdf
(Q 1.D)
Describe an efficient algorithm to ...
- 33
-2
votes
2
answers
223
views
Halting problem disproof
Introduction
This is a heavily updated question I have asked on this forum previously. I have understood and corrected the earlier errors and mistakes I made, and after doing that it still seems I ...
- 107
1
vote
2
answers
61
views
"Largest set" in coinductive definitions
In several explanations of coinductive definitions (for example, in the answers to What is coinduction?), we're told that while an inductive definition gives us the smallest set with a specified set ...
- 946
-4
votes
5
answers
401
views
Halting problem logic must be wrong
I think that I have found an issue with the proof of the halting problem, which would cause the entire proof to be invalid.
To ensure I understand, here is Turing's proof of the halting problem being ...
- 107
3
votes
0
answers
40
views
Can fine-grained hardness be proved directly from classical hardness (e.g., $\sf P \neq NP$) in some way?
I have just learnt about some typical result of fine-grained hardness in 15-455 by Prof Ryan: CNF-SETH implies ${\sf DIAMETER} \notin {\sf TIME}(mn^{1-\epsilon})$. (Here DIAMETER stands for the graph ...
- 301
-2
votes
1
answer
55
views
How to use Pumping Lemma $L = \{ wsw \mid w \in \{0,1\}^*, s \in \{2\}^* \text{, and } |w| = 2 \cdot |s| \}$?
I'm trying to use the Pumping Lemma to prove that $L = \{ wsw \mid w \in \{0,1\}^*,\ s \in \{2\}^*\text{ and } |w| = 2\cdot|s| \}$ is not a CFL.
2
votes
1
answer
162
views
How to evaluate the tightness of a bound on a function?
I recently submitted a paper where in part of the paper I derived a bound on a function (note it is an upper bound). The benefit of the bound is that it is much less complex to compute in contrast to ...
- 163
2
votes
0
answers
147
views
How would I prove that the algorithm to find the k-cores graph, produces a maximum size of vertices?
I came across this simple algorithm for finding a k-core of a graph, but every paper I read gives this notion of being maximal without proof, and I'm wondering how I might prove it.
So a k-core of a ...
13
votes
5
answers
4k
views
Proving Equivalence of Two Regular Expressions
Consider the regular expressions
$(1+01)^*(0+\epsilon)$
$(1^*011^*)^*(0+\epsilon) + 1^*(0+\epsilon)$,
where $\epsilon$ is the empty string. I need to determine if these expressions are equivalent. ...
- 257
1
vote
0
answers
76
views
Proof for Queue in BFS consists of vertices of distance k and k+1
For any vertex v reachable from s, BFS computes a shortest path
from s to v (no path from s to v has fewer edges).
In order to prove the above proposition, The author of the book has stated that we ...
- 11
0
votes
2
answers
112
views
Irregularity of $\{a^{b+cd} : d \in \mathbb{N}\}$
I was solving some basic problems about the theory of machines and automata. The topic was about pumping lemma, but I could not solve the below question and prove that it is not regular.
$$L=\{a^{b+cd}...
2
votes
2
answers
113
views
having trouble understanding the proof of regular expression identities $(u + v)^* = (u^*v)^*u^*$
I am having trouble understanding the proof given below:
\begin{align}
(u \cup v)^* &= (u^* \cup v)^* \\ &= u^*(u \cup v)^* = (u\cup vu^*)^* \\ &= (u^*v^*)^* = u^*(vu^*)^* \\ &= (u^*v)...
2
votes
1
answer
681
views
How to prove cycle sort has the minimum swap times?
Copy from Wikipedia
Cycle sort is an in-place, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array, unlike any ...
- 177
2
votes
2
answers
117
views
How do I prove the following invariant of this program?
I have been studying different topics within the realm of concurrent programming and came across "Lamport's bakery algorithm" which is based on the original version of the bakery algorithm ...
- 171
0
votes
0
answers
142
views
Language of Turing Machines that only accept their own encodings
Is the language $L = \{\langle M\rangle|L(M)=\{\langle M\rangle\}\}$ recursive?
I've been trying for hours to find a way to prove or disprove that it is.
My first attempt was to show it wasn't ...
- 1
0
votes
1
answer
26
views
Termination condition for max of array using divide and conuqer approach
I want termination proof of divide and conquer approach to find max of array,I want equational proof in form of lemma.Below is my attempt.I have got accepted everything in dafny ,it is only pointing ...
user139614
0
votes
1
answer
92
views
BST subtree value range
Suppose we have a node x in BST, and let max and min be the largest and smallest keys in the subtree rooted at x respectively. Prove that for any node n outside this subtree, the key of n is either ...
- 9
0
votes
1
answer
86
views
0
votes
3
answers
1k
views
Understanding proof that no DFA can recognize L with fewer than 2^k states
Let Σ = {a, b} and L = {ww | w ∈ Σ∗ and w is of length k}. Show that for each k, no DFA can recognize L with fewer than 2^k states.
What I understand is that we prove this by contradiction. Assume ...
1
vote
0
answers
384
views
Proof that if the residual network of a max flow has cycles then the max flow is not unique
Let $G = (V,E)$ be a directed graph with source $s$ and sink $t$ and $s \neq t$.
For each edge $e \in E$, we have $c(e) \in \Bbb N$.
also, we are given a max flow function $f$ on that network.
Let $...
- 11
0
votes
0
answers
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
1
answer
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 ...
- 11
0
votes
2
answers
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 ...
- 37
-3
votes
1
answer
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 ...
- 37
1
vote
1
answer
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?
- 37
1
vote
1
answer
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 ...
- 197
2
votes
1
answer
177
views
How to verify-: A language over Σ is also a language over any alphabet that is a superset of Σ?
Context-:
A language over Σ need not include strings with all symbols of Σ Thus, a language over Σ is also a language over any alphabet that is a superset of Σ.
https://www.univ-orleans.fr/lifo/...
- 23
0
votes
2
answers
110
views
Validity of proof by contradiction
I had a doubt in the proof by contradiction technique.
Under this technique, we assume the negation of what we want to prove as true, then show that assuming so generates a contradiction. Since a ...
- 1