23 long days I’ve waited to open this box up, and in less than 20 hours I will find out what’s behind door # 1. For now my appetite has been whetted by the calendar’s backdrop: Starkiller Base hovering over a Jakku littered with Star Destroyers, AT-ATs, and Christmas trees. That’s not quite how I …

# November 2017 archive

Nov 26 2017

## NFA and DFA Equivalence Theorem Proof and Example

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

## 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 …

Nov 17 2017

## Kleene’s Theorem

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

## Not String Theory – String Facts

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 …

Nov 07 2017

## 2017 LEGO Star Wars Advent Calendar #75184

If you want to get your hands on a LEGO Star Wars Advent Calendar, you need to buy it in early November. That is a lesson I learned the hard way last year. The downside of planning ahead is that once you’ve got it, it will be several weeks before you can tear into day …