Mar 14 2022
I got this to honor both that beautiful, irrational number, pi, and a beautiful, (mostly) rational human, my daughter Pi(per). Like every March 14th of the preceding 15 years, today I am celebrating both. Many thanks to Neil at Permanent Stain Tattoo for his outstanding work. If you are ever in Carlisle, PA and in …
Dec 07 2017
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 …
Dec 02 2017
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 …
Nov 26 2017
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 …
Nov 21 2017
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 …
Nov 17 2017
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 …
Nov 09 2017
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 …
Oct 12 2017
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 …
Jul 16 2017
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 …
Jan 29 2017
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 …
