Why is the number of states for DFA is 3n + 1 for this language

Question

I'm taking online compilers course. It's long ended, so it wouldn't be cheating to ask a question on quiz here.

Let $S_i$ be the string consisting of $i$ 0's followed by $2i$ 1's. Define the language $L_n = \{ S_i | 1 \leq i \leq n \}$. For example,

$L_3 = \{\, 011,\, 001111,\, 000111111\; \}$

For any given $n$, what is the smallest number of states needed for a DFA that recognizes $L_n$?

I know regexes a bit and I can't think of a way of expressing this with regular expression. But I thought even if it's possible it should involve some kind of backreference, and isn't backtracking impossible with DFA?

So the quiz gives the correct answer $3n + 1$ and explain it like so.

We need states to count how many 0 we meet and how many 1 we meet, so we need 3*n+1 states including the start state.

And this explanation doesn't explain anything to me. I mean okay the $+1$ part obvious, but why is there $3n$? I mean I agree that we probably need states to count how many 0 and 1 we meet, but exactly how we're gonna do it? If anything we should have 4 states in my opinion. One recognize 0, one to recognize 1 and another two states to count the numbers of them.

Right now I'm reading articles and papers about NFA, DFA, regular expressions and backreference, but maybe the answer is much simpler?

EDIT1. Okay, I've tried my best and constructed kind of obvious DFA for this task.

The total number of states would be $\sum_{i=1}^{n}i+2i$ which looks like arithmetic progression to me with a difference $d=(i+1)+2(i+1)-(i-2i)=i+1+2i+2-i-2i=3$ So the sum will be equal to $\frac{n(a_1 + a_n)}{2}=\frac{n(3 + (n + 2n))}{2}=\frac{n(3+3n)}{2}=\frac{3(n^2+1)}{2}$

I don't see $3n + 1$ here.

Okay, I think I finally got this. The main problem I think was that I haven't tried to actually draw automaton initially and If I would it would be much easier. So once I've noticed that it could be changed into this And this would give $3n+1$ obviously.

Answer 1

This is indeed a curious example. The reason why it works is the following (I show you on the example of $L_3$, but the argument is generic). Start with the minimal DFA accepting $\{S_n\}$, which clearly has $|S_n| + 1 = 3n + 1$ states. The states can be encoded by factorisations of $S_n$ in two factors (the reason of this encoding will appear shortly). Thus for $S_3$ you get $$ (\varepsilon, 000111111) \xrightarrow{0} (0, 00111111) \xrightarrow{0} (00, 0111111) \xrightarrow{0} (000, 111111) \xrightarrow{1} (0001, 11111) \xrightarrow{1} (00011, 1111) \xrightarrow{1} (000111, 111) \xrightarrow{1} (0001111, 11) \xrightarrow{1} (00011111, 1) \xrightarrow{1} (000111111, \varepsilon) $$ Now it is possible to accept the words $S_i$ by adding new transitions (but no new state!). For instance, if you want to accept $011$, you add the transition $(0, 00111111) \xrightarrow{\color{red}{1}}(00011111, 1)$ to get $$ (\varepsilon, 000111111) \xrightarrow{0} (0, 00111111) \xrightarrow{\color{red}{1}}(00011111, 1) \xrightarrow{1} (000111111, \varepsilon) $$ and to accept $001111$, you add the transition $(00, 0111111) \xrightarrow{\color{red}{1}}(000111, 111)$ to get $$ (\varepsilon, 000111111) \xrightarrow{0} (0, 00111111) \xrightarrow{0} (00, 0111111) \xrightarrow{\color{red}{1}}(000111, 111) \xrightarrow{1} (0001111, 11) \xrightarrow{1} (00011111, 1) \xrightarrow{1} (000111111, \varepsilon) $$ The trick is that you still get a deterministic automaton, due to the choice of the words added to the original automaton.

Answer 2

The explanation just gives some intuition. For a proof, you can use the Myhill-Nerode theorem for a lower bound, and a construction (a DFA for the language) for an upper bound.

In this particular case, the pumping lemma also shows a lower bound of $3n+1$ (once you realize that the pumping constant is the size of the minimal DFA). More generally, if $L$ is a finite language and the largest word in $L$ has length $m$, then the pumping lemma (or the Myhill–Nerode theorem) shows that any DFA for $L$ needs to have at least $m+1$ states.

You mention that you don't know how to express the language $L_n$ as a regular expression. Every finite language can be expressed as a regular expression by listing all of its word. For example, a regular expression for $L_3$ is $011+001111+000111111$.

Answer 3

As shown above, the DFA could be constructed like that. Every encountering an addition to the continuous 0 sequences, first traverse the additive 1's transition state, then reuse the previous path which is equally a counter to 0's number.

For the proof to the bound, It is deduced from the path the transition experiences.

To put it ahead, the DFA may not contains a self-cycle, for that the number of 0 or 1 is presumed to be restored. If there exists a self-cycle, it will not be able to figure out how many 0 or 1 there appears. Followed is the detailed proof of 3n + 1 lower bound.

First, for every single digit, it implies a directed path and a state transition. So as the longest number digits in the language, it has 3n digits. Plus the start state, there must be at least 3n + 1 state to traverse. So this gives the lower bound to the DFA. And the picture above shows one of the construction.