# Write down a DFA for the regular expression (000* + 111*)* and explain why it cannot have lesser number of states

So, I came up with a DFA for the regular expression. Now for every string described by the regular expression, the DFA accepts it. But in order to ascertain if it's really a DFA for the regex, you also need to know whether the reverse is true or not. Which is to say that the set of strings accepted by the DFA is described by the regex. I have no idea how to know if this is the case or not.

Could you guys tell me how to be sure if the DFA really recognizes the language described by the regex (000* + 111*)*

• Could you please at least rotate the image so people don't have to cock their head sideways while reading the question? – dkaeae Aug 19 '19 at 11:48
• Possible duplicate of How to convert finite automata to regular expressions? – dkaeae Aug 19 '19 at 11:48
• @dkaeae I disagree. Any method I'm aware of to convert automata to regular expressions produces horrifically long expressions and won't help the asker at all. This is a completely different question, about proving that an automaton accepts all strings within a given language and rejects all strings not in it. – David Richerby Aug 19 '19 at 17:36

(1) You are convinced that all the strings decribed by the RegEx are accepted by the DFA. In order to conclude equality you want to know the converse. Is every string accepted by the DFA also described by the RegEx? To do this, try to argue that every string accepted by the DFA consists of "blocks" of each time at least two the same letter. This is not very dificult: the states of the DFA here "count" symbols $$0$$ and $$1$$.
(2) In the title of the question you ask whether the number of states is minimal. This can be done by arguing the no states can be merged. This can be shown by giving for each pair of states a string that "distinguishes" the states: states $$p$$ and $$q$$ are distinguished if there is a string $$w$$ such that $$w$$ from one of $$p$$ and $$q$$ reaches an accepting state, while it does not reach an accepting state from the other.
Here this can be done by looking at most one letter ahead: can be reach an accepting state by $$\lambda$$, $$0$$ or $$1$$? For each of the six staes the answers are different.