I will be upfront about this. I am not a gamer: PC, console, mobile or otherwise. But, as I’ve mentioned in a previous post, like every pre-teen and as it tuns out, many adults, I was bitten by the Fortnite bug earlier this year. With not an X-Box nor Playstation to my name and no sign of a mobile version on the horizon at the time, I was limited in the platforms I could choose from to play it on. So I fired up my recently retired MacBook Pro, slapped a fresh coat of Windows 10 on it, and hit Epic’s site for the free Battle Royal download.

Jul 07 2018

## CoPrA – An Asyncronous Python Websocket Client for Coinbase Pro

I know it’s too much too hope that I have any regular readers, but if you come here even infrequently you may have noticed it’s been seven months since I last posted. You may even have wondered what I have been up to. What could’ve possible kept Tony so busy that he would totally ignore his blog for more than half a year? Well, I’ll tell you. Fortnite. I have been busy getting my ass kicked 24-7 by eleven year-olds in Fortnite. It is embarrassing quite honestly.

In between matches, however, I actually have been productive working on intelligent agents for trading cryptocurrency on the Coinbase Pro (formerly GDAX) exchange. While most of the high level code isn’t ready for prime time yet, a good portion of the low level, workhorse code has been road tested and is relatively stable. Since other developers might find it useful, I’ve decided to begin releasing it into the wild.

Dec 07 2017

## The Pumping Lemma for Regular Languages

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 used to prove, often using proof by contradiction, that a language is not regular. In this sense the Pumping Lemma provides a necessary condition for a language to be regular but not a sufficient one.

Dec 02 2017

## Necessity and Sufficiency

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 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!

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.

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.

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

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 arrays of one or more binary bytes. In programs, they can be stored in variables or constants, and often show up in source code as literals, ie., fixed, quoted values like “salary” or “bumfuzzle.” (That is my new favorite word, btw.) Outside of occasionally navigating the subtleties of encoding and decoding them, I never gave strings a second thought.

Even when I first dipped my toe into the waters of natural language processing, aka NLP (not to be confused with the quasi-scientific neuro linguistic programming which unfortunately shares the same acronym), I still really only worked with strings as whole entities, words or affixes, As I made my through familiarizing myself with existing NLP tools, I didn’t have to dive any deeper than that. It was only when I started programming my own tools from the ground up, did I learn about the very formal mathematics behind strings and their relationship to sets and set theory. This post will be an attempt to explain what I learned.

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 can be written as a propositional formula, a sentence in propositional logic. A binary Boolean function, a Boolean function with two arguments, can be described by one out of sixteen canonical formulas.

Sep 27 2017

## The Three Pro-Human Laws of Robotics

From Vienna Bienalle 2017, taking place this week in Austria, comes a new take on Isaac Asimov’s Three Laws of Robotics. The head of the project, Christoph Thun-Hohenstein, says the update was necessitated by:

…the need for benign intelligent robots and the necessity of cultivating a culture of quality committed to serving the common good!

That sounds a lot like Asimov’s reasoning, but the new laws are certainly worthy of consideration and debate.