# Tag Info

### How to prove greedy algorithm is correct

Ultimately, you'll need a mathematical proof of correctness. I'll get to some proof techniques for that below, but first, before diving into that, let me save you some time: before you look for a ...
• 160k
Accepted

### Why are mathematical proofs so hard?

I feel like i am memorizing the proofs rather than learn how to prove You can't learn "how to prove". "Proving" is not a mechanical process, but rather a creative one where you ...
• 13.3k
Accepted

### Proving Equivalence of Two Regular Expressions

One way to prove that two regular expressions $r_1,r_2$ generate the same language is to show both inclusions: Show that if $w$ is generated by $r_1$ then it is generated by $r_2$. Show that if $w$ ...
• 277k

### Does contradiction definitively prove nonexistence

A proof is a proof, even if the system you work in is inconsistent. So if you prove that the existence of a decider leads to contradiction, you have proved that such a decider does not exist. If in ...
• 30.5k

### False proofs that look correct

One of my favourites is the "brothers paradox": https://en.wikipedia.org/wiki/Boy_or_Girl_paradox I tell it as I learned it*, as follows: in a village, each family has two children, elder ...
• 17.2k
Accepted

### Prove that A** = A*, where A is a language over Σ*

Since $L \subseteq L^*$ for all $L$, we have $\mathcal{A}^* \subseteq \mathcal{A}^{**}$. In the other direction, suppose that $w \in \mathcal{A}^{**}$. Then there exists an integer $n \geq 0$ and ...
• 277k