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!

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.

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.

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 »

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.

In my last post about binary signed integers, I introduced the ones complement representation. At the time, I said that the ones complement was found by taking the **bitwise complement** of the number. My explanation about how to do this was simple: invert each bit, flipping 1 to 0 and vice versa. While it’s true that this is all you need to know in order to determine the ones complement of a binary number, if you want to understand how computers do arithmetic with signed integers and why they represent them the way they do, then you need to understand what complements are and how the method of complements allows computers to subtract one integer from another, or add a positive and negative integer, by doing addition with only positive integers.

LIDAR (**LI**ght **D**etecting **A**nd **R**anging) sensors play a critical role in almost all autonomous and semiautonomous vehicles. Using lasers and relatively simple time of flight calculations, LIDAR can very accurately measure distances and generate detailed 3D maps of environments, but traditionally the best performing systems have been large and very expensive. German lighting manufacturer Osram Opto Semiconductors unveiled their new 4 channel LIDAR package last week, and its price and size is set to shake up the market.

In the last post, we saw that one of the major failings of the signed magnitude representation was that addition and subtraction could not be performed on the same hardware as for unsigned integers. As I pointed out, the reason for this is because negating a number in signed magnitude does not yield the additive inverse of that number. The ones complement representation eliminates this issue, although it does introduce new, subtle issues, and [spoiler] doesn’t address the problem of having two representations for zero.

South Korean scientists from the Department of Materials Science and Engineering at Pohang University of Science and Technology appear to have cleared the largest obstacle to the feasibility of building brain-like computers: power consumption. In their paper “Organic core-sheath nanowire artificial synapses with femtojoule energy consumption,” published in the June 17th edition of *Science Advances*, the researchers describe how they use organic nanowire (ONW) to build synaptic transistors (STs) whose power consumption is almost one-tenth of the real thing.

If you’ve just installed the Arduino IDE on Ubuntu, you’ve likely encountered an error similar to the one above the first time you tried to upload a sketch to your board. The error that I specifically get reads:

```
avrdude: ser_open(): can't open device "/dev/tty/ACMO": Permission denied
ioctl("TIOCMGET"): Inappropriate ioctl for device
Problem uploading to board. ...
```

I got this error today while doing a fresh install of Arduino 1.6.8 on Ubuntu 15.10, aka Wily Werewolf, but I’ve also run into it on previous Ubuntu versions as well. As I suspect this is not the last time I’ll encounter it, I figure I should write up the solution here instead of having to hunt it down again the next time it stumps me.

Continue reading »