**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?

###### Asked By : Mahesha999

###### Answered By : rici

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.

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

**3200 people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback