I know that the answer is $15$ states, but I cannot get my mind to understand why is that? which property makes it impossible to do it in less states? I've tried to mess with it for a long time and still can't find the property that forces me to use $15$ states.
This also seems true for all DFA's of these type, if it accepts strings of length $x$ or $y$, then the number of states it needs is $xy$.
I would really appreciate it if someone could tell me the specific reason of why this happens?
Asked
Active
Viewed 861 times
1
Pwaol
- 2,113
-
1Do you know how to prove that if you replace "$3$ or $5$" by $7$, you need $7$ states? – markvs Mar 04 '22 at 09:31
-
1For the second part of your question, the answer is not $xy$, but $\text{lcm}(x,y)$. – J.-E. Pin Mar 04 '22 at 17:33
-
@markvs I don't really know how to formally prove these things or how this proof looks like, but I can understand intuitively that we need to save the knowledge of when does the length become divisible by $7$, and for that we must have $7$ states – Pwaol Mar 06 '22 at 10:55
-
You may want to use syntactic monoids of these languages. – markvs Mar 06 '22 at 12:37
-
Look at such papers: https://www.researchgate.net/publication/226652130_On_Deterministic_Finite_Automata_and_Syntactic_Monoid_Size – markvs Mar 06 '22 at 12:42
-
Indeed, look at Theorem 2 here: https://cse.buffalo.edu/~regan/cse681/notes/lectureA03.pdf – markvs Mar 06 '22 at 12:57
-
Does this answer your question? Building a Deterministic Finite Automaton with the set {a} – markvs Mar 06 '22 at 17:45
-
@markvs The linked question is different since it is just asking for a DFA, but this one asks for the minimal DFA. – J.-E. Pin Mar 06 '22 at 19:52