# Tag Info

144

Translating Code to Mathematics Given a (more or less) formal operational semantics you can translate an algorithm's (pseudo-)code quite literally into a mathematical expression that gives you the result, provided you can manipulate the expression into a useful form. This works well for additive cost measures such as number of comparisons, swaps, statements,...

69

To my knowledge the pumping lemma is by far the simplest and most-used technique. If you find it hard, try the regular version first, it's not that bad. There are some other means for languages that are far from context free. For example undecidable languages are trivially not context free. That said, I am also interested in other techniques than the ...

62

Proof by contradiction is often used to show that a language is not regular: let $P$ a property true for all regular languages, if your specific language does not verify $P$, then it's not regular. The following properties can be used: The pumping lemma, as exemplified in Dave's answer; Closure properties of regular languages (set operations, concatenation, ...

62

First, to dispel a possible cognitive dissonance: reasoning about infinite structures is not a problem, we do it all the time. As long as the structure is finitely describable, that's not a problem. Here are a few common types of infinite structures: languages (sets of strings over some alphabet, which may be finite); tree languages (sets of trees over some ...

57

Before I answer your general question, let me first take a step back, give some history background, and answer a preliminary question: Do non-computable functions even exist? [notational note: we can relate any function $f$ with a language $L_f=\{ (x,y) \mid y=f(x) \}$ and then discuss the decidability of $L_f$ rather than the computability of $f$] ...

57

It all comes from undecidability of the halting problem. Suppose we have a "perfect" dead code function, some Turing Machine M, and some input string x, and a procedure that looks something like this: Run M on input x; print "Finished running input"; If M runs forever, then we delete the print statement, since we will never reach it. If M doesn't run ...

50

Yes, if you can come up with any of the following: deterministic finite automaton (DFA), nondeterministic finite automaton (NFA), regular expression (regexp of formal languages) or regular grammar for some language $L$, then $L$ is regular. There are more equivalent models, but the above are the most common. There are also useful properties outside of the ...

48

There is no magic bullet; NP-hardness proofs are hard. However, there is a general framework for all such proofs. Many students who struggle with NP-hardness proofs are confused about what they're supposed to be doing, which obviously makes it impossible to figure out how to do it. So here is what to do to prove a problem NP-hard. First, unless you're ...

45

Ogden's Lemma Lemma (Ogden). Let $L$ be a context-free language. Then there is a constant $N$ such that for every $z\in L$ and any way of marking $N$ or more positions (symbols) of $z$ as "distinguished positions", then $z$ can be written as $z=uvwxy$, such that $vx$ has at least one distinguished position. $vwx$ has at most $N$ distinguished ...

37

Based on Dave's answer, here is a step-by-step "manual" for using the pumping lemma. Recall the pumping lemma (taken from Dave's answer, taken form Wikipedia): Let $L$ be a regular language. Then there exists an integer $n\ge 1$ (depending only on $L$) such that every string $w$ in $L$ of length at least $n$ ($n$ is called the "pumping length") can be ...

34

Closure Properties Once you have a small collection of non-context-free languages you can often use closure properties of $\mathrm{CFL}$ like this: Assume $L \in \mathrm{CFL}$. Then, by closure property X (together with Y), $L' \in \mathrm{CFL}$. This contradicts $L' \notin \mathrm{CFL}$ which we know to hold, therefore $L \notin \mathrm{CFL}$. This is ...

34

Converting Full History to Limited History This is a first step in solving recurrences where the value at any integer depends on the values at all smaller integers. Consider, for example, the recurrence $$T(n) = n + \frac{1}{n}\sum_{k=1}^n \big(T(k-1) + T(n-k)\big)$$ which arises in the analysis of randomized quicksort. (Here, $k$ is the rank of the ...

32

To put it more concretely, if I have an approach to prove P≠NP and if I could construct oracles to make a situation like above happen, why does it make my method invalid? Note that the latter “if” is not a condition, because Baker, Gill, and Solovay already constructed such an oracle. It is just a mathematical truth that (1) there exists an oracle relative ...

31

Execution Counts of Statements There is another method, championed by Donald E. Knuth in his The Art of Computer Programming series. In contrast to translating the whole algorithm into one formula, it works independently from the code's semantics on the "putting things together" side and allows to go to a lower level only when necessary, starting from an "...

28

From Wikipedia, the pumping language for regular languages is the following: Let $L$ be a regular language. Then there exists an integer $p\ge 1$ (depending only on $L$) such that every string $w$ in $L$ of length at least $p$ ($p$ is called the "pumping length") can be written as $w = xyz$ (i.e., $w$ can be divided into three substrings), satisfying ...

28

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 proof, try random testing. Random testing As a first step, I recommend you use random testing to test your algorithm. It's amazing how effective this is: in my ...

27

Generating Functions $\newcommand{\nats}{\mathbb{N}}$ Every series of numbers corresponds to a generating function. It can often be comfortably obtained from a recurrence to have its coefficients -- the series' elements -- plucked. This answer includes the general ansatz with a complete example, a shortcut for a special case and some notes about using this ...

22

First, let us make two maybe obvious, but important assumptions: _.random_item can choose the last position. _.random_item chooses every position with probability $\frac{1}{n+1}$. In order to prove correctness of your algorithm, you need an inductive argument similar to the one used here: For the singleton list there is only one possibility, so it is ...

21

Let us consider the following inductive definition: \qquad \displaystyle \begin{align*} &\phantom{\Rightarrow} \quad \varepsilon \in \mathcal{T} \\ w \in \mathcal{T} \quad &\Rightarrow \quad aw \in \mathcal{T}\\ aw \in \mathcal{T} \quad &\Rightarrow \quad baw \in \mathcal{T} \end{align*} What is $\mathcal{T}$? Clearly, the set of ...

21

There is (at least) one way to prove unambiguity of a grammar $G = (N,T,\delta,S)$ for language $L$. It consists of two steps: Prove $L \subseteq \mathcal{L}(G)$. Prove $[z^n]S_G(z) = |L_n|$. The first step is pretty clear: show that the grammar generates (at least) the words you want, that is correctness. The second step shows that $G$ has as many syntax ...

21

You show that either model can simulate the other, that is given a machine in model A, show that there is a machine in model B that computes the same function. Note that this simulation does not have to be computable (but usually is). Consider, for example, pushdown automata with two stacks (2-PDA). In another question, the simulations in both directions ...

21


18

There is a huge variety of feasible approaches. Which is best suited depends on what you are trying to show, how much detail you want or need. If the algorithm is a widely known one which you use as a subroutine, you often remain at a higher level. If the algorithm is the main object under investigation, you probably want to be more detailed. The same can ...

Only top voted, non community-wiki answers of a minimum length are eligible