"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*automaton and I'll explain later why.

_{2,2}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:

*A*and for convenience I'll rewrite it to look like this instead.

_{2}Wait, how is this related to the initial problem? Well, if we look closer at

*A*we observe that we can build a similar structure to that of

_{2,2}*A*'s out of this simpler automaton.

_{2,2}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*. See, the two indices (

_{2,3}*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*would look like.

_{2,2,2}*Special thanks to Mr. Sipos together with whom I cracked this late in the evening years ago.*

## No comments:

## Post a Comment