[Solved]: minimum number of states for the regular expression

Problem Detail: 

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

Asked By : anirudh

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37100

3.2K people like this

 Download Related Notes/Documents