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*)* DFA for (000* + 111*)*

  • 1
    $\begingroup$ Could you please at least rotate the image so people don't have to cock their head sideways while reading the question? $\endgroup$ – dkaeae Aug 19 '19 at 11:48
  • 3
    $\begingroup$ Possible duplicate of How to convert finite automata to regular expressions? $\endgroup$ – dkaeae Aug 19 '19 at 11:48
  • 2
    $\begingroup$ @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. $\endgroup$ – David Richerby Aug 19 '19 at 17:36

You state two questions.

(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.

  • $\begingroup$ Regarding the second point, I understand the procedure you have stated. But, why does this work? As far as I understand, for two states to be "independent", they should represent totally different conditions of the system whose behavior is totally decoupled from each other. So, in a sense, the minimal number of states in the DFA for a language represents the degrees of freedom the expressions of the language has. Which is to say, all the expressions of a language can be grouped into that number of classes and each class has same behavior. How does this connect with what you just described? $\endgroup$ – Shashank Kumar Aug 20 '19 at 14:44
  • $\begingroup$ Classes that can be distinguished in a (regular) language are described by the Myhill-Nerode Theorem. In a deterministic automaton the states form a refinement of these classes. Distinguishing states that can be merged into one are the subject of minimization algotithms. Distinguishing states by finding strings such that exactly one of the two states leads into an accepting state is the method used by Hopcrofts algorithm. $\endgroup$ – Hendrik Jan Aug 21 '19 at 15:01

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.