Tag Archives: mathematics

A Better Approach to DFA Minimization

DFA minimization is often described as follows:

  1. First eliminate any unreachable states (easy).
  2. Then create a table of all possible pairs of states \((p, q)\), initially unmarked. (E.g. a two-dimensional array of booleans, initially set to false.) We mark pairs \((p, q)\) as and when we discover that \(p\) and \(q\) cannot be equivalent.
    1. Start by marking all pairs \((p, q)\) where \(p \in F\) and \(q \not\in F\), or vice versa.
    2. Look for unmarked pairs \((p, q)\) such that for some \(u \in \Sigma\), the pair \((δ(p, u), δ(q, u))\) is marked. Then mark \((p, q)\).
    3. Repeat step 2.2 until no such unmarked pairs remain. If \((p, q)\) is still unmarked, can collapse \(p\) and \(q\) to a single state.

Source: Mary Cryan, Informatics 2A: Processing Formal and Natural Languages, Lecture 5, 2018.

Based on my very limited research, aforementioned algorithm seems to be the most common way of teaching undergrads how to minimise a given DFA, but I believe that it suffers from reasons soon listed below, and I will instead propose a better way of executing the same algorithm that does not (make the student) suffer from the same problems.

Continue reading

Closed-Form Expression to Calculate n-th Fibonacci Number

A more interesting way to find nth Fibonacci number.

Fibonacci sequence is a prime example in teaching recursion to newcomers, and a great opportunity to brag if your language supports Tail Call Optimization, but it often goes unnoticed that there is a closed-form expression which lets us find the nth Fibonacci number with great ease and in much faster way. This article will present the expression, and explain -step by step- its derivation using high-school mathematics.

Continue reading