Dec 05 2017

Day 5 – Resistance Officer

Resistance Officer Minifigure

I have mixed feelings about today’s offering. It is a Resistance officer minifigure, and I generally like all minifigures. But it’s also about as generic as a minifigure can be. I don’t remember leaving the theater after The Force Awakens and talking with my daughter about how awesome the Resistance officers were. But then again he does have the same haircut as me. I guess I ultimately lean toward liking it but only by a hair.

Continue reading

Dec 04 2017

Day 4 – Blaster Cannon

Finally a build not from Rebels. Well, it’s not from Rebels per se because Day 4’s blaster cannon is generic enough that it could have been from any Star Wars movie or animated series. I remember seeing the the Snowtroopers lugging and setting up one of these when they assaulted the rebel base on Hoth, so I’m going to say it’s from The Empire Strikes Back. Yay! The Advent calendar gave us one from the original trilogy, and the best movie from the entire series by far.

Continue reading

Dec 03 2017

Day 3 – The Phantom

I’m beginning to think that it might be Rebels all the way down. It’s day 4 of the LEGO Star Wars Advent calendar, and we’ve got another spaceship from the animated series Rebels. Although it was eventually lost over the gas planet of Yarma, the modified VCX-series auxiliary starfighter known as the Phantom served Ezra Bridger and his crewmates of the Phantom’s mothership, the Ghost, well during the early days of the rebellion. I’m pleased to have built the Phantom since you really can’t have the Ghost without the Phantom (or the Phantom II now) even if today’s build is not the same scale as the Ghost from Day 1.

Continue reading

Dec 02 2017

Necessity and Sufficiency

Necessity - Sufficient Venn DiagramAm 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 sufficiency and their rigid definitions in the domain of mathematical logic. If you are only interested in looking for meaning in your life then move along, but if you are one of the enlightened few that knows that math really is the answer to every question, then by all means, read on!

Continue reading

Dec 02 2017

Day 2 – Sabine Wren

Day 2 of the LEGO Star Wars Advent calendar is keeping it Rebels, and that is more than ok with me. Minifigures are my favorite, and Mandalorian warrior turned rebel Sabine Wren is a new one for my collection.

Continue reading

Dec 01 2017

Day 1 – The Ghost

Day 1 is finally here, and it was well worth the wait. The first build from the 2017 LEGO Star Wars Calendar is a mini version of The Ghost from the animated series Rebels. Piloted by Hera Syndulla, The Ghost has, in the three short years of the cartoon’s, run become as iconic as any other in the Star Wars universe.

Continue reading

Nov 30 2017

Day 0 – Inside the Box

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 remember The Force Awakens, but for LEGO Star Wars I’ll let it slide.

Continue reading

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 exists, there will be just one transition and obviously as a result, one follow up state. For a given string, the path through a DFA is deterministic since there is no place along the way where the machine would have to choose between more than one transition.  Given this definition it isn’t too hard to figure out what an NFA is. Unlike in DFA, it is possible for states in an NFA to have more than one transition per input symbol. Additionally, states in an NFA may have states that don’t require an input symbol at all, transitioning on the empty string ε.

Superficially it would appear that deterministic and non-deterministic finite state automata are entirely separate beasts. It turns out, however, that they are equivalent. For any language recognized by an NFA, there exists a DFA that recognizes that language and vice versa. The algorithm to make the conversion from NFA to DFA is relatively simple, even if the resulting DFA is considerably more complex than the original NFA.  After the jump I will prove this equivalence and also step through a short example of converting an NFA to an equivalent DFA.

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 are one and the same when it comes to describing regular languages. In the post I will provide a proof of this groundbreaking principle.

Continue reading

Nov 17 2017

Kleene’s Theorem

Stephen Kleene

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 regular expressions is intimately familiar with an indispensable operator that resulted directly from his work and even bears his name, the *, or as it is formally known, the Kleene star.

While his contributions to computer science in general cannot be overstated, Kleene also authored a theorem that plays an important role in artificial intelligence, specifically the branch known as natural language processing, or NLP for short. Kleene’s Theorem relates regular languages, regular expressions, and finite state automata (FSAs). In short, he was able to prove that regular expressions and finite state automata were the same thing, just two different representations of any given regular language.
Continue reading