# minimum number of states for the regular expression

Could somebody please tell me if there is a way to create a DFA with 8 states for the regular expression $$(111 + 11111)^*$$ I was able to create a DFA with 8 states, but the place I saw the question has answer as 9 states. And if possible, could you please show me the DFA.

Thanks

• I would be curious to see your 8 state solution... – J.-E. Pin Jan 9 '15 at 14:38
• I've added my 8 state DFA, could you please tell if there is anything wrong with it. I'm not able to find any... – anirudh Jan 9 '15 at 15:01
• Your proposed automaton is nondeterministic (the initial state has two transitions on 1). – Shaull Jan 9 '15 at 15:08
• oh...sorry about that...crazy mistake.. thanks for your help – anirudh Jan 9 '15 at 15:16
• DFAs can be minimized, which produces a unique (up to isomorphism) minimal equivalent DFA. – reinierpost Jan 9 '15 at 17:05

We can summarize this unary language by the list of possible lengths of words: $$0,3,5,6,8,9,10,11,12,\ldots.$$ Now let us look at (left) shifts of this list: $$0,3,5,6,8-\infty \\ 2,4,5,7-\infty \\ 1,3,4,6-\infty \\ 0,2,3,5-\infty \\ 1,2,4-\infty \\ 0,1,3-\infty \\ 0,2-\infty \\ 1-\infty \\ 0-\infty$$ There are 9 different shifts, and so 9 different states in the minimal DFA. In this case, the minimal DFA is very simple: it has 9 states $s_0,\ldots,s_8$, with arrows $s_i \to s_{i+1}$ (for $i < 8$) and $s_8\to s_8$, starting state $s_0$, and accepting states $s_0,s_3,s_5,s_6,s_8$.
This sort of reasoning works for all unary languages, though sometimes the minimal DFA won't be a simple path. For languages of the form $(1^{n_1}+\cdots+1^{n_k})^*$, the minimal DFA is in fact always a path, and assuming (without loss of generality) that $\mathrm{gcd}(n_1,\ldots,n_k)=1$, the number of states exactly equals $2$ plus the maximal integer not representable as a sum of non-negative multiples of $n_1,\ldots,n_k$ (in our case, $7$).