World's most popular travel blog for travel bloggers.

Does preparing min DFA by combining equivalent states always result in min DFA

, ,
Problem Detail:

I know the following fact:

If \$Ma_N=\{w:n_a (w)=Nk,k≥0\}\$, then Number of states in \$\$Ma_{N1}×Ma_{N2} =Ma_{N1}∪Ma_{N2} =Ma_{N1}∩Ma_{N2} =Ma_{N1}-Ma_{N2} =LCM(N1,N2)\$\$ where \$n_a (w)\$ is the number of occurrences of \$a\$ in \$w\$

I recalled the example I solved: the DFA for the language \$(111+11111)^*\$. It was given as follows: It was backed by the fact that Any number greater than 8 can be factored into sum of 3s and 5s.

Q.1 Can we interpret this language as union of two: \$(111)^*\cup (11111)^*\$?

Q.2 If yes, then should forming union DFA by forming product DFA (and making desired states final as required by union operation) of above two languages \$(111)^*\$ and \$(11111)^*\$ and then applying DFA minimization by finding equivalent states result in 9 states? I tried it as below using JFLAP (product DFA on left and auto generated min DFA on right). But I didnt get 9 states. Instead I got number of states \$=LCM(3,5)=15\$ states. Q.3 So can we conclude we cannot always get minimum DFA by the approach of combining equivalent states (may be especially when the DFA can be simplified using some mathematical insights)? Or did I made some mistake?

The answer to Q1 is no.

\$1^{11}\$ is in \$(1^3 + 1^5)^*\$, but not in \$(1^3)^* + (1^5)^*\$

I think that leads to the remaining confusions.