Theory of Computation - Finite State Automata


An honest effort in tackling the fundamentals of program design must include an understanding of the basics of computation best embodied by automata theory, and our chosen software ecosystem fortunately makes available to us a rich set of visualization tools to assist us in learning these abstract concepts.

We will begin this investigation by utilizing a great library called automat, built specifically for this task, which will allow us to use AT&T's Graph-Visualization software to turn simple expressions into images to represent models of algorithms.

The simplest automaton is a chain of valid inputs, like [1 2 3]. We punch that into automat, and it spits out a nice pretty diagram for us: 
> (view [1 2 3])


And then we can combine them:
> (view (a/or [1 2 3] [1 3]))
This represents the union of the two automata, and returns an automaton which will either accept [1 2 3] or [1 3].

Game designer Mark Engelberg, creator of instaparse, gave a brilliant demonstration of how this can be used to elegantly solve a classic programming puzzle called Maximum Segment Sum.

First we will state the problem:

Find the maximum sum achievable by adding up a segment of a sequence of numbers (typical input is a mix of positive and negative integers).

For example, the maximum-segment-sum of [-1 2 3 -4 5 -8 4] is 6,
because 2+3+-4+5 is 6.

Want to see the whole thing?

Comments

Post a Comment

Popular posts from this blog

MilkyTracker: The quest for the perfect music software

Image
The last album I made was in 2013 on a MacBook using Logic Pro and Massive, a setup that cost a couple thousand dollars. Since I no longer have that machine and the software was proprietary, I no longer have access to all of that work. This has sparked a great interest in searching for a replacement digital audio suite, one that would provide a comparable workflow but also offer longevity, the ability to archive my work in a format that can be shared across platforms and improved upon. An artist should demand nothing less! What if a painter had to stop working on everything because they didn't want to use canvas from a certain company, and then none of their brushes or paints would work? That's what is actually happening in today's creative landscape, but with software. Whatever program I use must, above all else, use a standard file format for music encoding, which is usually MIDI but there are others. That way none of my work is dependent on any specific piece of ...
Read more

Programming: The New Rock 'N' Roll

Image
In this post we will set up a super efficient programming environment - on a $10 computer, in just a few short lines of code! Step 1 - Install tmux , a terminal multiplexer. This will allow us to work in as many simultaneous terminal windows as we need to, just as if we are in a graphical desktop but all from a single text console: sudo apt install tmux Begin a session with the "tmux" command. Open a new window with Ctrl-b c and switch between them with Ctrl-b n. Step 2 - Install leiningen , vim and fireplace (formerly called "foreplay"). They work together with the Clojure programming language, which uses an extremely concise syntax to generate highly optimized Java and Javascript code: sudo apt install vim git clone https://github.com/ctford/vim-fireplace-easy.git .vim ln -s ~/.vim/vimrc.vim ~/.vimrc vim -c "helptags ~/.vim/bundle/vim-fireplace/doc" -c "q" (Paste the contents of this file into /bin/lein) sudo ...
Read more

Pardon My Parsing...

Image
Advent of Code 2016 problems Since they all involve parsing some kind of input data, this will be a job for ... Instaparse ! With it we can use a context-free grammar to generate a tree-like structure from our data. For example, here an input string for the day 4 problem. Each room is represented as a key, id and checksum: aaaaa-bbb-z-y-x-123[abxyz] The key is made of one or more strings of letters separated with hyphens. The id is a string of numbers, and the checksum is a string of letters in brackets. This is how we represent that in EBNF notation... In Clojure!: (def room-parser (insta/parser "room = key id checksum key = (word <separator>)+ <separator> = '-' word = #'[a-zA-Z]+' checksum = <'['> word <']'> id = #'[0-9]+'")) Now we pass the input to our shiny-new parser: (room-parser "aaaaa-bbb-z-y-x-123[abxyz]") And we get our magical tree! Ooowee! => [:...
Read more