Micah Brown is a student at The Nueva School, also the host of Project80, among other things.

Milton Freedman is an economist.

MMSE is not mean squared error! It is a short mental state test to measure one’s neuralpsycological capabilities; frequently used as a first line by a psycologist.

The fact that DFAs are limited, it allows us to optimize a DFA. Specifically, we ask: “does this DFA have a minimal number of states?”

Formally: can we accept the same language with a particular DFA with another DFA with less states?

For every language \(L\), there is a unique (up to state relabeling) minimal-state DFA \(M^{*}\) such that \(L(M^{*}) = L\).

Furthermore, there exists an efficient algorithm which, given DFA \(M\), will produce this unique \(M^{*}\).

“minimum edit distance” is one approach to solving the problem of “how similar are these two strings”? minimum edit distance is defined by the smallest number of editing operations (insertion, deletion, substitution) needed to transform one string into another.

There are two technical definitions. Both definitions are grounded upon “minimum number of operations it takes to transform a string into another, where”

edit distance with DP

DP costs \(O(nm)\), backtrace costs \(O(n+m)\).