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.

• It seems that you're almost there. Why don't you think about it a little more? Don't give up so fast. Commented May 2, 2016 at 18:10
• 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 Commented May 3, 2016 at 21:15
• Yes, that's the idea. Commented May 3, 2016 at 21:52
• Perhaps you can answer your own question now? Commented May 3, 2016 at 22:26