DFA problems

When learning about automata, you might stumble upon this classical problem which pops up in books, lecture notes and articles:
"Construct a DFA that accepts the strings containing an even number of 1s and 0s"

The classic solution I've seen associated with the problem is the following:

I'll call this the A_2,2 automaton and I'll explain later why.

We can easily check that this is the minimal automaton for this particular language.
However, I've never seen anyone try to tear this automaton apart and explain how one would reach it. Sure, you could find a non-deterministic automaton first that solves the problem, convert it to a deterministic one, and finally minimize it, but building it from scratch is far nicer.

First, let's consider a simpler, but related problem for example:
"Construct the DFA that accepts the strings containing an even number of 1s"

Of course, the solution to this trivial problem is the following:

I'm naming this A₂ and for convenience I'll rewrite it to look like this instead.

Wait, how is this related to the initial problem? Well, if we look closer at A_2,2 we observe that we can build a similar structure to that of A_2,2's out of this simpler automaton.

Just take these two automata

Multiply them and that's it!

It turns out that an automaton that accepts "an even number of Gs" AND "an even number of Bs" is the result of multiplying the automaton that accepts "an even number of Gs" with the automaton that accepts "an even number of Bs"


Let's now generalise this!
"Construct a DFA that accepts the strings containing k*2 Rs and k*3 Gs (for any natural number k)"

Following the recipe, we first need to build the automata that accept the two sublanguages and then multiply them.

I'll call this A_2,3. See, the two indices (2 and 3) indicate the length of the cycles.

Can this scheme be extended to fit a third symbol? Yes, of course! Let's see how A_2,2,2 would look like.

Special thanks to Mr. Sipos together with whom I cracked this late in the evening years ago.

WebGL is good for your health

Here's a totally random link I've happened to find on the internet: https://3d.casinofloor.com/.

What is this you might say?! Am I trying to lure you to some online casino and get incredibly wealthy? Well, that, and take a closer look at the link - it says "3d"! Now click on the link, wait 2 seconds for it to load and feast your eyes on one of the biggest tech-demos showing off WebGL - it's a 300 meter long cathedral-like casino containing a ton of slot machines, animated characters, particles, reflective water, gazillions of bottles and glasses, spooky statues and a never-ending sunset.

As far as I'm aware there are only 2 other neat demos out there showing off huge environments in WebGL. The first is the Epic Citadel demo by the makes of the Unreal engine and the second is Bananabread. These 2 are initially coded in C++ and then transpiled in asm.js flavoured JavaScript. Wait, why are people in this age coding in C++ and then spitting out javascript-machine-code-wannabe apps on the web? Plain JavaScript is fast and mature enough to develop in and drive huge applications as well - as proof,  the Casinofloor demo uses the Goo Engine which is written from scratch in JavaScript.

tl;dr? Short version: goo.js rules and check out the little snippet below:

Meanwhile...

I've been a bit absent/slow on this blog and I'm terribly sorry, but I've grown out of my bedroom now, I'm not a "bedroom programmer" any more, I got a job and I program among other programmers (in an office!). I'm working at Goo Technologies and as a Goonian I have the honour of contributing to GooJS (a really cool JavaScript-WebGL-3D-eyepopping-library) (oh, and yes, we at Goo prefix everything with "goo").

And in the weekends I still manage to push updates on MUPLex.

One of the most important additions to MUPLex is a type-inferencer-checker-thing. The language is still dynamically typed (I love dynamic typing), but because the default/preferred bindings in the language are immutable and because there are no implicit conversions, a static code analyser can have a look at the code, infer the possible types of expressions and throw warnings when it concludes that some bits of code can never execute properly if they're reached.

Another addition is that MUPLex now has a to-javascript transpiler. Yes, I am contributing to the 87563284762 languages that compile to JS nowadays. One of the hardest bits was to find a translation scheme that generates pretty expression-ish looking JS code (even compiled code has to be pretty) and not generate any _var_7a62ff variables. It actually generates no extra variables. MUPLex has some features like implicit currying, lexical scoping and a module/namespace system, but JS is flexible enough that you can emulate these relatively easy.

"In the future, in the year 2000" I'm looking forward to showing what awesomeness you can achieve with GooJS and you can expect more updates on MUPLex, but not that often.

Introducing MUPLex

I've been taking one of Dan Grossman's courses on programming languages and it was one of the most illuminating I've ever taken. While teaching, he used a made up programming language called MUPL. This MUPL had higher order functions, pairs, conditionals and the addition operation - this is the bare minimum with which you can teach how to build interpreters but also enough on which you can further build a high level functional language.

MUPLEx is basically an extensions of MUPL. It adds some syntactic sugar as well as new features. Here's a list:

• Functions with an arbitrary number of arguments
• Currying by default
• Mutability - yes, I know mutability is the source of all evil (most of it, at least) but in some cases it makes sense, like having lazy evaluation or memoization
• Records - to be able to build meaningful data structures
• More math operations
• Letrec - the equivalent of forward declaration in C (this way you can have mutually recursive functions, or other useful constructs)
• Cond - syntactic sugar for nested conditionals
• Lists - syntactic sugar for nested pairs
• A way to print out stuff
• Booleans

It also has some primitive type checking to catch some errors as you type. But, unfortunately, at this stage the errors are not too explicit.

I can't include the interpreter in this post because it's a pretty hefty beast, but I can point you to the github HTML preview thingie or directly to the repository.
*the preview may not work in Chrome/Safary

Spring updates, RU invades the GPU

Spring has come! (for most at least, Sweden is actually a bit behind). So here's some spring news:

Firstly, I've updated the stochastic optimization framework. The plugin system is now fully functional - yes, you can pack your favourite algorithm into a .jar, drop it in the plug-ins folder and see how it performs. The usual bug fixes here and there also come with this update.

Secondly, I've updated and shared Particle48 on github. It's a particle systems library (for JS & the HTML5 canvas) I made a while ago for use at LD events (and I've actually used it in Homo Vermes). I expect to update it before every LD compo and add new types of particles. If I get fellow ludumers to contribute, things will really start rolling.

And last but not least, OCLEx got 2 new additions: 1. a simple demo to the bundle to show how to set things up to start doing some image manipulation on the GPU and 2. RU on the GPU - this basically means that every Executor is a separate "process" running on the GPU and doing its duty. It started as an experiment to see how one would simulate a MIMD architecture in a SIMD environment and then got disguised in a nice RU uniform. Early OpenCL capable video cards have terrible performance penalties if the kernels are not executing the same instruction. This is a big bummer if you have any sorts of branches in the kernels. With this simulation you don't get any performance penalties (everything runs slower, but it's independent of the instructions the kernels are executing). I'll come back with more details after I do some more work and prettify it. In the mean time you can find it here.

The screenshot looks like that not because it's a work in progress but because it uses the GL_UGLY texture filter.

Return of the Four Fours

In an attempt to get faster results for the four fours problem mentioned earlier, I've come up with a simpler algorithm that does even more number crunching but somehow computes the precious list faster. Despite being sillier because it computes the same thing twice (or even worse), it'll use waaay less memory.
Oh, and since the algorithm encodes the solutions as stacks of operations, it'll print them accordingly (in reverse polish notation).

I want to see all three four five six seven ones twos threes fours fives sixes sevens eights nines tens

Four fours

The "Four fours" problem has probably wasted many people's time... As I recently rediscovered the fun in solving this, but I didn't have the patience to figure out how to get more than 2 or 3 values, I started writing a program for it instead. Supposedly, computers are better at number crunching.

It takes about 2 15 seconds to compute five fours on my super-speedy 1.0 GHz AMD not-even-sure-it's-Turing-complete thing. However, trying with seven fours is only for the brave and the patient. The algorithm stores partial results in some huge matrix to reduce computation time, but I have a feeling that this has consequences (especially in JavaScript).

I want to see all three four five six seven ones twos threes fours fives sixes sevens eights nines tens