Wednesday 29 January 2014

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 A2,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 A2 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 A2,2 we observe that we can build a similar structure to that of A2,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 A2,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 A2,2,2 would look like.
Special thanks to Mr. Sipos together with whom I cracked this late in the evening years ago.