decidability of a given language

Question

The language EGAL is $\{(A,B): A \text{ and } B \text{ are DFAs with } L(A) = L(B)\}$

How do I prove that such language is decidable by testing every word of $A$ and $B$ until a defined length ?

i need a hint to start. thanks

Answer 1

HINT: Suppose that $A$ has $n_A$ states, $B$ has $n_B$ states, and $n=\max\{n_A,n_B\}$. Show that if $A$ and $B$ accept exactly the same words of lengths $\le n$, then $A$ and $B$ accept the same languages. Thinking about the proof of the pumping lemma or the Myhill-Nerode theorem is helpful here.