Category: Math

Dec 07 2017

The Pumping Lemma for Regular Languages

Pumping Lemma DFA

There are two versions of the Pumping Lemma. One is for context free grammars and one is for regular languages. This post is about the latter. The Pumping Lemma describes a property that all natural languages share. While it cannot be used by itself to prove that any given language is regular, it can be …

Continue reading

Dec 02 2017

Necessity and Sufficiency

Necessity - Sufficient Venn Diagram

Am I sufficient? Am I even necessary? If you’re plagued by these existential questions and have ended up here in your quest for an answer, then I’ve got some bad news for you. The answer to both is no. I keed. I keed. Actually, the bad news is that this post is about necessity and …

Continue reading

Nov 26 2017

NFA and DFA Equivalence Theorem Proof and Example

NFA N

Finite state automata (FSA), also known as finite state machines (FSM), are usually classified as being deterministic (DFA) or non-deterministic (NFA). A deterministic finite state automaton has exactly one transition from every state for each possible input. In other words, whatever state the FSA is in, if it encounters a symbol for which a transition …

Continue reading

Nov 21 2017

Proof of Kleene’s Theorem

In my last post, “Kleene’s Theorem,” I provided some useful background information about strings, regular languages, regular expressions, and finite automata before introducing the eponymously named theorem that has become one of the cornerstones of artificial intelligence and more specifically, natural language processing (NLP).  Kleene’s Theorem tells us that regular expressions and finite state automata …

Continue reading

Nov 17 2017

Kleene’s Theorem

Stephen Kleene

Stephen Cole Kleene was an American mathematician who’s groundbreaking work in the sub-field of logic known as recursion theory laid the groundwork for modern computing.  While most computer programmers might not know his name or the significance of his work regarding computable functions, I am willing to bet that anyone who has ever dealt with …

Continue reading

Nov 09 2017

Not String Theory – String Facts

Strings

As a computer programmer for more than a quarter of century, I don’t think I have ever thought much about strings. I knew the basics. In every language I’d worked with, strings were a data type unto themselves. Superficially they are a sequence of characters, but behind the scenes, computers store and manipulate them as …

Continue reading

Oct 12 2017

Binary Boolean Logic Functions

Boolean functions, sometimes also called switching functions, are functions that take as their input zero or more boolean values (1 or 0, true or false, etc.) and output a single boolean value. The number of inputs to the function is is called the arity of the function and is denoted as k. Every k-ary function …

Continue reading

Jul 16 2017

The Sum of an Arithmetic Series

An arithmetic sequence of numbers, sometimes alternatively called an arithmetic progression, is a sequence of numbers in which the difference between all pairs of consecutive numbers is constant. A very simple arithmetic sequence consists of the natural numbers: 1, 2, 3, 4, … where the difference between any number and the number before it is …

Continue reading

Jan 29 2017

The Method of Complements

Abraham Lincoln once famously said, “Everybody loves a compliment.”  I suspect that if he had been a mathematician he would have loved complements, too. We’ve already seen what complements are and talked about the two most prolific: the radix complement and the diminished radix complement. Now it’s time to explore how we can leverage complements …

Continue reading

Jan 10 2017

Number System Complements

In my last post about binary signed integers, I introduced the ones complement representation. At the time, I said that the ones complement was found by taking the bitwise complement of the number. My explanation about how to do this was simple: invert each bit, flipping 1 to 0 and vice versa. While it’s true that …

Continue reading