0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Q.1. No. $(111)^*\cup(11111)^*$ can't represent $11111111$. $\endgroup$
    – Rick Decker
    Feb 29, 2016 at 20:46

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\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.