1
$\begingroup$

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.

$\endgroup$
  • $\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$ – Yuval Filmus May 2 '16 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$ – Don Fanucci May 3 '16 at 21:15
  • $\begingroup$ Yes, that's the idea. $\endgroup$ – Yuval Filmus May 3 '16 at 21:52
  • $\begingroup$ Perhaps you can answer your own question now? $\endgroup$ – Yuval Filmus May 3 '16 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.