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.

Filter by
Sorted by
Tagged with
-1
votes
1answer
392 views

How to prove this language is regular [duplicate]

Let $L$ be a regular language with alphabet $\Sigma = \{a,b,c\}$. Prove that the following language is regular: $\{w | w \in L \text{ and } w \text{ starts with } abc \}$. I wonder what proof ...
0
votes
0answers
26 views

Avoiding pumping lemma [duplicate]

Is there a way to show $\{a^nb^nc^n:n\geq0\}$ is not regular without pumping lemma?
1
vote
1answer
86 views

Is $A_{PTM}$ a BPP-complete language?

The language $A_{PTM}$ is defined as the acceptance problem on a Probabilistic Turing machine. $A_{PTM}=$ { $<M, x> | M$ on input $x$ accepts with an error probability less than or equal to 1/...
0
votes
1answer
42 views

Prove a language $A_{PTM}$ is not BPP-Complete

I am trying to prove that there are a language is not BPP-Complete. There are a couple of examples online, but they are not the best examples and are a bit complicated. I spoke with one of my computer ...
1
vote
0answers
61 views

Why does the proof that #SAT is in IP stop after m rounds?

I've been struggling to understand why the interactive proof for #SAT stops after only $m$ rounds, where $m$ is the number of variables in the formula $\phi$. I understand that two polynomials of ...
1
vote
2answers
235 views

A question about an input in a Halting Problem proof

Here is my Halting Problem proof, that largely mirrors other (non-diagonalizing) proofs that I've seen. $H(p,i)$ returns $1$ if program $p$ halts on input $i$. $H(p,i)$ returns $0$ if program $p$ ...
1
vote
2answers
355 views

Induction rules for reflexive, transitive closure

I'm trying to solve an exercise on inductive definitions, the premiss is: Let $\to$ be a relation on $A$ and $\to^*$ its reflexive, transitive closure, which is defined by following two rules: $a \...
-1
votes
2answers
87 views

Can someone help me understand this proof: there exists a complement of an RE language is not RE

I'm trying to understand this proof in Peter Linz's book The math just doesn't make any sense, I don't understand how this is a proof. First of all, the author says let's define a language such that: ...
1
vote
1answer
290 views

Understanding how to decide whether a language for a DFA is decidable

So from what I understand, if a language is recognisable then using a TM it can be accepted and halted or rejected or halted, however a language that is decidable can be accepted and always halts on ...
2
votes
0answers
136 views

Find, with proof, the number of distinct graphs with the vertex set $V = \{1, 2, \ldots,n\}$ [closed]

Let $n \in \mathbb{Z^+}$. Find, with proof, the number of distinct graphs with the vertex set $V = \{1, 2, \ldots,n\}$. We say two such graphs are distinct if one of them has an edge $(u, v)$ and the ...
-1
votes
2answers
172 views

Is this a valid proof of uncomputability of a function that doesn't use diagonalization?

Let's take the function $f = \{(0,\pi)\}$. If I want to prove that such function is uncomputable I can simply say that calculating $\pi$ from $0$ would necessarily require infinitely many steps,...
4
votes
1answer
376 views

How to use structural induction to prove law on lists

I want to prove that the following equation holds using structural induction on (finite) lists ...
0
votes
1answer
133 views

Where I can find example how prove red black tree?

I need prove that any red-black tree with at least two elements obtained through the insertion algorithm has at least one red node. For this, I need use Induction. I don't understand how apply ...
1
vote
0answers
390 views

Minimal number of states

In a recent IT class we got the task of creating a finite state automaton that accepts only the words "auto" "automarke" "tomaten" and "automaten" and no others. Basically the whole class had no ...
3
votes
1answer
107 views

Proving laws of take and drop functions using structural induction on lists

I'm trying to prove the following laws using structural induction on (finite) lists: ...
1
vote
1answer
136 views

Collision resistant Hash function in chaos cryptography

In my earlier Question asked here Help in understanding how to apply nonlinear function in hashing about chaos cryptography, since then I have come across several research papers that apply atleat ...
1
vote
0answers
255 views

Given a context free grammar, prove if the grammar is ambiguous

Here is a context free grammar that I have been given for practice: Grammar $G = (V,\Sigma,R,S)$ where $V$ is $\{S,A,B,a,b,c\}$ and $\Sigma$ is $\{a,b,c\}$. $R$ has the following rules: $$\begin{...
2
votes
1answer
279 views

Prove the equivalence between a CFG and a Context free language

I have to prove that the language $L=\{a^ib^j:2i=3j+1\}$ and the CFG G with the following rewrite rules: $S\rightarrow a^2Tb$ $T\rightarrow a^3Tb^2 |\epsilon$ are equivalent to each other. I'm ...
5
votes
2answers
145 views

Nominal unification: How this lemma is proved?

I was reading nominal unification paper. I could not understand the proof of a lemma. The paper is here nominal unification. The lemma is following. $\sigma$ is a substitution, $\pi$ is a permutation ...
4
votes
1answer
342 views

How to prove equivalence relation in this case?

I am working on $\lambda$-terms and trying to prove the $=$ is an equivalence relation on $\lambda$-terms. My problem is proving reflexive relation. $\frac{}{\theta \vdash x = x}$ $\frac{ \theta,x \#...
3
votes
2answers
94 views

what is routine induction?

I read a paper which mentioned routine induction many times. But when I google it, there are nothing showed up. I think routine induction means the induction on the structure, analyzing possible ...
3
votes
1answer
899 views

Every LEFT-RESET Turing machine has an equivalent conventional Turing machine

I am working on a proof of the theorem that every LEFT-RESET Turing machine has an equivalent conventional, single tape Turing machine. The transitions for the LEFT-RESET Turing machine are {Right, ...
1
vote
2answers
553 views

Proof Idea: How to prove the intersection of regular language and CFL is a CFL?

I know that the intersection of a regular language and a context free language is a context free language. I've seen this fact proven on here and other websites. However, after spending hours reading ...
2
votes
1answer
791 views

CFL and inverse homomorphism

I found a proof that shows CFL is closed under inverse homomorphism. First of all the Definition of an homomorphism and its inverse: $h: \Sigma^{*} \rightarrow \Delta^{*} \ \ \ h(L) = \{h(w) |w \in ...
2
votes
0answers
107 views

Formalizing an intuitive linear programming proof

My professor has asked me to prove the following: Prove that we can use an algorithm for linear programming to solve linear inequality feasibility problems. The number of variables and ...
2
votes
2answers
1k views

Proving at least $n-1$ comparisons are needed to test if an array is sorted

so I need to prove the following: Prove that $n-1$ comparisons are sometimes necessary to test whether an array with $n$ distinct elements is sorted in increasing order, for any $n \geq 1$. The ...
2
votes
1answer
166 views

Is the search for a k-Hamiltonian Path NP-hard?

A $k$-Hamiltonian Path is an Hamiltonian Path where each node (but the last $k$ nodes on the path) is connected to his $k$ successors, and the last $k$ nodes are connected to all of their successors. ...
0
votes
1answer
424 views

Support of a codeword in a binary linear code proof

Let $C$ be the binary linear code with the following generator matrix $G= \begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & ...
1
vote
1answer
38 views

Linear Bound Automaton Power

Please tell me is their deterministic linear bound automaton same power as non-deterministic linear bound automaton to recognize any language?
1
vote
1answer
2k views

Proving that a problem is in NP

I have an assignment in which the problem, $D$, is simple but, once found, easy to check. Is it enough to prove that a solution $x$ can be checked in polynomial time to prove that $D \in NP$? (The ...
0
votes
0answers
229 views

Writing a constructive proof for closure of a regular language under homomorphism

I've spend the last few days searching online for an example of a constructive proof of regular languages being closed under homomorphism, but I have not seen one. I am mostly unsure of how to show ...
1
vote
2answers
60 views

Can you apply the induction hypothesis to its outcome?

Assume a well-founded relation $<$ over a set $S$ and a property $P$ on $S$ such that: $P$ holds for all minimal elements of $S$. For every $b \in P$ and $a < b$ we have: if $P(a)$ then there ...
2
votes
2answers
125 views

The floor function [closed]

How do I prove or disprove the following statements: $$(a) ∀n ∈ \mathbb N, ∃k ∈ \mathbb N, ∀x ∈ \mathbb R , \lfloor nx \rfloor − n \lfloor x \rfloor ≤ k$$ and $$ (b)\exists k \in \mathbb N, \forall n \...
0
votes
1answer
2k views

How would you prove a family of functions is universal?

A set of functions from a universe U of keys to n buckets is universal if for every pair of keys in U, say x and y, such that x != y, the probability of h(x) = h(y) is less than or equal to 1/n, for a ...
3
votes
1answer
743 views

Red-Black tree height from CLRS

The lemma 13.1 of CLRS proves that the height of a red black tree with $n$ nodes is $$h(n) \leq 2\log_2(n+1)$$ There's a subtle step I don't understand. The property 4 reported at the beginning of ...
2
votes
2answers
361 views

Prove L = {a = b ⊕ c | a, b, c ∈{0, 1}*} is not regular

Given that language $L = \{a = b ⊕ c \mid a, b, c ∈ \{0,1\}^*, a = b \oplus c\}$, with an alphabet $Σ = \{⊕, =, 0, 1\}$, I need to prove that this language is not regular. The following is as far as I ...
1
vote
1answer
5k views

Pumping Lemma: 1^n^2 is not regular

I am attempting to prove via the pumping lemma that $1^{n^2}$ is not a regular language. I started with $w = 1^{p^2}$ I then divided $w$ into $xyz$, where: $x = 1^{l}$ $y = 1^{m}$ $z = 1^{{p^2}-...
2
votes
0answers
274 views

Analysis of the long division algorithm in the Knuth book (Seminumerical algorithms) 1

I've been reading through the long division algorithm exposed in the Knuth book for a week and I still miss some details. There's an implementation of such algorithm in "Hacker's Delight" by Warren, ...
2
votes
2answers
283 views

How can I prove that a cryptography algorithm is a pseudo-random number generator?

I have read about cryptography prgs. If I have a generator G(x1,x2...,xn)= x1,x2,...,xn, x1&x2...&xn , how can I prove that it is a prg or prove it is not? Is there some principles I have ...
0
votes
1answer
136 views

If $L\in\mathrm{NP}$ is $\mathrm{coNP}$-complete, then $\mathrm{coNP}=\mathrm{NP}$

The problem in the title is to be proven, and while proving $\mathrm{coNP}\subset\mathrm{NP}$ is rather clear given the assumptions (see below), I fail to see a way to prove $\mathrm{NP}\subset\mathrm{...
3
votes
2answers
63 views

Given the hash of a collection, H(X), can I build a proof that F(X) == Y, without having X?

Given a cryptographic fingerprint of a collection, K == hash(X), an arbitrary function F, and a value ...
5
votes
1answer
55 views

Is it possible to build short proofs of arbitrary folds over a huge list?

With the use of Merkle Trees, you can prove the presence of an element of a very big list, with an amount of information close to just logarithm of the size of the whole tree. Merkle proofs, thus, ...
3
votes
1answer
793 views

How to prove a greedy algorithm that uses the longest increasing subsequence?

Here is the thing, I am solving an problem, and I think, say, I am pretty sure that I have the correct algorithm but I haven't been able to prove it because of my lack of practice prooving greedy ...
4
votes
1answer
317 views

Prove foldl fusion law

I have proven the foldr Fusion Law as follows: Given f is strict, f a = b and ...
3
votes
1answer
77 views

Do formulas involving fewer repetitions of variables give higher numerical precision?

I'm having some trouble doing SICP exercise 2.15. Please note that this question is not closed related to Lisp. Instead, it's closely related to numerical analysis. Exercise 2.15. Eva Lu Ator, ...
7
votes
2answers
154 views

Why Church-encoded types aren't sufficient to express inductive proofs?

I've heard some claims that the calculus of constructions without inductive types isn't powerful enough to express proofs by induction. Is that correct? If so, why isn't the Church-encoding sufficient ...
2
votes
1answer
33 views

Can an alphabet be extended in a reduction proof? (with sample problem)

So I am working on solving a problem on whether following language is decideable: $L = \{n \in \mathbb{N} \mid M_n$ never freezes (for any input)$\}$, where $n$ is the Gödel-number of a Turing ...
1
vote
1answer
141 views

Proof that language is not context-free with Parikh's theorem

I want to prove that the language $L = \{ a^{n}(ab)^{{n}^{2}}b^{n} \mid n \geq 0 \}$ is not context-free by using Parikh's theorem. My first assumption is that the $(ab)^{{n}^{2}}$ part cannot be ...
0
votes
1answer
70 views

NFA automata with ϵ moves proof

let's say L is a regular language. And there in an NFA automata with epsilon moves A,in which for every accepting state δ(q,σ)=Ø. How can I prove that there must be an automata A as defined for L?
6
votes
1answer
3k views

Why proving programs correctness doesn't have the same importance as algorithms analysis or the theory of computation in practice?

What are the major causes that makes "Proving Programs correct", not a widely attractive subject? though from it's name, and from what we know from other disciplines (like mathematics) it looks like ...