Cheap and Secure Web Hosting Provider : See Now

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

, , No Comments
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:

enter image description here

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.

enter image description here

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.

Best Answer from StackOverflow

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

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback