1
$\begingroup$

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

enter image description here

$\endgroup$
  • $\begingroup$ I would be curious to see your 8 state solution... $\endgroup$ – J.-E. Pin Jan 9 '15 at 14:38
  • $\begingroup$ 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... $\endgroup$ – anirudh Jan 9 '15 at 15:01
  • 1
    $\begingroup$ Your proposed automaton is nondeterministic (the initial state has two transitions on 1). $\endgroup$ – Shaull Jan 9 '15 at 15:08
  • $\begingroup$ oh...sorry about that...crazy mistake.. thanks for your help $\endgroup$ – anirudh Jan 9 '15 at 15:16
  • $\begingroup$ DFAs can be minimized, which produces a unique (up to isomorphism) minimal equivalent DFA. $\endgroup$ – reinierpost Jan 9 '15 at 17:05
4
$\begingroup$

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

$\endgroup$

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.