November 2017 archive

Nov 30 2017

Day 0 – Inside the Box

2017 LEGO Star Wars Advent Calendar #75184 Box - Inside Background

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 …

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

Nov 07 2017

2017 LEGO Star Wars Advent Calendar #75184

2017 LEGO Star Wars Advent Calendar #75184 Box - Front

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 …

Continue reading