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 …

# Category: Artificial Intelligence

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 …

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 …

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 …

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 …

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

Nov 28 2016

## AI Creates Videos of Future Events

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

Jun 27 2016

## Google Refreshes Asimov’s Three Laws of Robotics

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 …

Jun 23 2016

## Researchers Create Low-Power Nanowire Artificial Synapses

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