beanz Magazine

Finite Automata

Pstmn on Flickr

Learn about the smallest, simplest computers and where they’re still used today.

Computer scientists like to study kinds of computers. That’s not surprising, it’s in the name. But what might be a little surprising is that “computer” doesn’t only mean an object like a desktop or smartphone! No, the kinds of “computers” that computer scientists study include a bunch of different theoretical machines that are simulated with just a pen and paper, each with different abilities and restrictions on what it can do. These range from the mighty Turing machine, a nearly century old pen & paper “computer” that has infinite memory, to the tiniest, smolest, machine called a finite automata. The finite automata happen to be the subject of our article.

Finite automata are so simple, actually, that we can build and simulate one with just a few circles and lines drawn on paper. All a finite automata is capable of is processing a series of inputs one after the other and then responding “yes” or “no”. Here’s our first example, which is a finite automata that answers the question “is this binary number even?”

I’ve already implied that you can “run” this machine with a pen & paper, so let’s describe how! We start at the circle on the left with the arrow pointing into it and then feed the machine one input at a time. In this case, those inputs are digits of the binary number. For each input, follow the arrows between the different circles, or states. If, after we’ve eaten all the digits of the number, we’re in a double circle then the answer is “yes” but if we’re in only a single circle the answer is “no”.

The logic of this automata is that if a binary number ends in a 0 then the number is even, but if it ends in a 1 the number is odd.

Let’s try an example! Run the automata on the input “1010”, which is 10 in decimal. If you need a refresher on binary, check the further reading links!

  1. You start in the “odd” state and the first character is a 1, so you loop back into the “odd” state.
  2. The next character is a 0, so you move into the “even” state.
  3. The next character is a 1, so you move back into the “odd” state.
  4. The last character is a 0, so you move into the “even” state and stop. This means the number is even!

To test yourself, try a few other binary numbers like “111”, which is 7 in decimal, or “11010” which is 26 in decimal.

Okay, but what else are finite automata good for? They’re used under the hood of a lot of software as very efficient ways to calculate the answers to all sorts of questions like “Does this email address end with either ‘.com’ or ‘.org’?” which is solved by the following automata. Note the use of the “*” symbol as a shorthand for “any character” rather than drawing a separate loop for every letter, number, and symbol.

Or this one that tests a solution to a Legend of Zelda style maze where you have to move through a specific set of exits or get sent backwards:

These automata are all just pen & paper simulations of machines but you can implement them inside any programming language. They’re used all the time for efficiently executing regular expressions, which are a popular tool for searching & matching text.

Computer scientists have another interest in finite automata, though, because we like to know how much power different models of computation have. This means we don’t just want to know what it can do but what it can’t do.

To that end, see what goes wrong if you try to write a finite automata that answers the question “is this word a palindrome?”. Maybe think about what’s the simplest feature you could add to a finite automata that would let it answer the question.

So that’s our introduction to finite automata, the simplest kind of computing machine we can define. They’re shockingly powerful for how simple they are and even more shockingly close to being real computers.

Try writing some and seeing what you can do!

Learn More

Reference on binary

https://learn.sparkfun.com/tutorials/binary/all

Spoilers for the kind of automata that can detect palindromes

https://en.wikipedia.org/wiki/Pushdown_automaton

Finite state automation

http://encyclopedia.kids.net.au/page/fi/Finite_state_automaton

Finite state automation lesson

http://www.mathmaniacs.org/lessons/fsm/index.html

Treasure hunt

https://www.stem.org.uk/elibrary/resource/32382

Also In The February 2020 Issue

Please note: all issues back to February 2017 are available to subscribers only.
The December 2016 and earlier issues are open and free to access.

Can you figure out how to divide up coconuts between a group of sailors and a monkey? This puzzle mixes math and coding. Plus you can go online to try the code yourself!

Recreate the classic game in this simple Python tutorial. What whimsical stories can you write?

If you like ships, then you’ll love this easy-to-use website that keeps track of seafaring vessels around the world. Bonus: it helps prevent maritime collisions!

Ready for some good old-fashioned winter fun? In this article, build a digital snowman with Sketchup.

A fun, silly way to share your coding trials and triumphs with friends — because everything is better with kittens!

Should you learn Python, Scratch, Java, Assembly? If you’re feeling overwhelmed by too many options, this article is here to help.

Illustrating computational concepts like decomposition and algorithms with simple, hands-on, and occasionally messy activities.

In the old days, before video game systems had cameras and sensors, programmers had to get creative.

Six women were hired to use their math skills to program the ENIAC computer. They called themselves The First Programmers Club.

Learn about the key software that keeps your computer safe from viruses.

Programs are constantly being patched and improved. How do we keep track of all this new code?

Dive into the nitty-gritty details of binary numbers: how they work, why they’re used, and where they come from.

An easy way to code your own 3D graphics online. Dive into the world of pixels, triangles, textures, and colours!

Learn about the smallest, simplest computers and where they’re still used today.

Interesting stories about science and technology for February 2020.

Links from the bottom of all the February 2020 articles, collected in one place for you to print, share, or bookmark.