5
$\begingroup$

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. enter image description here

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 enter image description here And this would give $3n+1$ obviously.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Haven't read all of your answer, but I think you've put me on the right track. See my second edit. $\endgroup$ – user1685095 Oct 31 '16 at 10:13
  • $\begingroup$ I don't think I agree with this answer.. I understand your thinking and I picked this answer too when I was solving this question. However, according to this solution we would be reusing FINAL states.. maybe it's just an issue with the elaboration of the question.. $\endgroup$ – thiagoh Apr 2 '17 at 3:25
  • $\begingroup$ @thiagoh What do you mean by "reusing final states"? $\endgroup$ – J.-E. Pin Apr 2 '17 at 9:13
  • $\begingroup$ @J.-E.Pin I mean that this DFA may have many final (accept) states, visually identified by double circles, for example; and final states in this case will reused as many arrows are coming. This way a string such as "0011" will end up being acceptable. Did you get it? $\endgroup$ – thiagoh Apr 2 '17 at 20:12
  • $\begingroup$ @thiagoh Sorry, but I have no idea what you mean as there is only one final state, namely $(000111111, \varepsilon)$. $\endgroup$ – J.-E. Pin Apr 3 '17 at 9:10
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Okay, this doesn't explain anything to me. And I don't think that to understand the answer in this course I'm supposed to know Myhill-Nerode thm. Could you show what would NFA and DFA look like for this language? Also of course I understand that I can just write down language as listing all of its words, but how to express that compactly? We clearly see the concept of n zeros followed by twice as ones. How can that be expressed as a regex? If it would be n zeros followed by twice the number of zeros I could write (0*)\1{2} for example. $\endgroup$ – user1685095 Oct 31 '16 at 8:03
  • $\begingroup$ I could show you what a DFA for the language looks like, but I choose not to, since I believe that you can do so yourself; a DFA would use $3n+2$ states, and an NFA would use $3n+1$ states. Regarding the lower bound (why at least $3n+1$ states are needed), you will get the intuition once you construct the DFA/NFA; for anything more than that, you have to get more technical. $\endgroup$ – Yuval Filmus Oct 31 '16 at 8:29
  • $\begingroup$ I've constructed obvious DFA for that, It haven't helped. $\endgroup$ – user1685095 Oct 31 '16 at 9:57
  • $\begingroup$ Try constructing a DFA for $0^n1^{2n}$ first. Then modify it to a DFA for $L_n$ without increasing the number of states. $\endgroup$ – Yuval Filmus Oct 31 '16 at 10:05
0
$\begingroup$

enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ This only shows automata with $3n + 1$ many states exist. It does not prove the bound holds. $\endgroup$ – dkaeae Jan 8 at 8:49
  • $\begingroup$ This seems to accept, incorrectly, the string $0011$. $\endgroup$ – Rick Decker Jan 9 at 0:38
  • $\begingroup$ @RickDecker Sorry for that, It has been repaired now. $\endgroup$ – Harvee Jan 14 at 3:24
  • $\begingroup$ @dkaeae I have added the proof. The answer is edited. $\endgroup$ – Harvee Jan 14 at 3:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.