I was given the following question.

Given a minimal DFA $A$ with $m$ states over some alphabet $\Sigma$ which is a "black box" (you can only run words to it and it tells you if it accepts or not):

a) describe an algorithm that allows you to find the equivalence classes of the Myhill-Nerode relation and then,

b) describe how you can reconstruct $A$ using the equivalence classes.

I managed to solve the first part using a brute force algorithm that checks all the words with length at most $m$. So now I have the equivalence classes but I don't know how to solve (b), how to reconstruct the DFA and its transition function. I think of looking at the representing words of the classes in lexicographic order then choosing the $m$ states from left to right corresponding to the words as an encoding, then the accepting states will be the states of the words which the black box automaton accepts and $q_0$ will be the state of $\epsilon$'s equivalence class which clearly is an equivalence class. But now the hard part is the transition function.

  • $\begingroup$ It seems that you're almost there. Why don't you think about it a little more? Don't give up so fast. $\endgroup$ Commented May 2, 2016 at 18:10
  • $\begingroup$ I think I know how to do this but please confirm that this is true I think that i know the start state and from there i can check for each letter of the alphabet to which equivalence class it moves ϵ and then the transition function from q0 will be so and then i wil ldo so for every other state until I cover from every state all the trasitions with any letter exist. please confirm me that this is true. @YuvalFilmus $\endgroup$ Commented May 3, 2016 at 21:15
  • $\begingroup$ Yes, that's the idea. $\endgroup$ Commented May 3, 2016 at 21:52
  • $\begingroup$ Perhaps you can answer your own question now? $\endgroup$ Commented May 3, 2016 at 22:26


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.