Nov 262017
 

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 212017
 

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 »

Sep 272017
 

Robot holding human skullFrom 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.

Continue reading »

Jun 092017
 

Boston Dynamics

Boston Dynamics, the MIT spin-off and self-proclaimed maker of “nightmare-inducing robots“, has been sold by its parent company Alphabet (aka Google) to the Japanese tech behemoth SoftBank. No specifics regarding the price or the terms of the sale have been announced which is not surprising given we still don’t know how much Google paid for the company when it purchased it four years ago.

Continue reading »

Nov 282016
 

Minority Report

Set 38 years in the future, the plot of 2002’s blockbuster film Minority Report revolves around Washington DC’s PreCrime unit, a police force who able to stop future murders from happening with the aid of three mutant human who are able to predict homicides before they happen.  Minority Report managed to side step the “psychic predicts a murder” cliché storyline with its innovative use of technology: not only could precogs predict future murders, but their visions could be streamed via a neural bridge in the form of a video that the police officers could watch. Fantastical? Nope, and researchers from MIT already have a jump on the technology.

Continue reading »

Nov 142016
 

Osram Scanning LIDARLIDAR (LIght Detecting And Ranging) 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.

Continue reading »

Jul 052016
 

Sharper Image camera drone

I visit the local Michaels store at least once a week. Even if I didn’t have a 10 year old daughter with an insatiable appetite for arts and crafts, I imagine that I would still make that 5 minute crosstown trip weekly. The reason is simple: coupons. In their weekly circular, without fail, they always include a handful of coupons, and even though I am not that artsy crafty myself, I can usually find something useful for my lab. From resin and epoxy to tools and storage, I never come home empty-handed. Most of the time the coupon is for 40% off any regularly priced item, and sometimes it’s even 50%, but the rare, and often most useful coupon is the 20% off any item – regular OR sale price. It was because of such a coupon that I came unexpectedly home with a Sharper Image camera drone.

Continue reading »

Jun 272016
 
Google Research Logo

Research at Google

Ever since their introduction over eighty years ago, Isaac Asimov‘s Three Laws of Robotics have been the de jure rules governing the acceptable behavior of robots. Even the uninitiated and uninterested are likely to say they know of them, even if they can’t recite a single rule verbatim. When conceived, the Three Laws were nothing but a thought experiment wrapped in a science fiction story, but now, the dizzying pace of developments in the fields of robotics and ai has spurred engineers and ethicists to reinvestigate and rewrite the guidelines by which artificially intelligent entities should operate.  Who better to take the lead in this initiative than Google, the company who just yesterday announced that machine learning will be at the core of everything it does.

Continue reading »