I have a $NFA$ named $A$, with number of states $n$.
And I got another $NFA$ name $B$ with number of states $k$.
I want to check $L(A)=L(B)$.
My question is how long should I go. What is the longest word I should check.
Let say $\exists x:\forall w\in \Sigma^*, |w|<x: A(w)=B(w)$
which means if $A$ accept $w$ so do $B$ and the other way around.
how big should be $x$ so I can tell for sure that $L(A)=L(B)$?
I think it somewhere around $max(2^n,2^k)$ but have no clue how to prove it.
Thanks
Let us determenize both $A$ and $B$ into $C$ and $D$ with $2^n$ and $2^k$ states (and make sure that sets of states of $C$ and $D$ are distjoint) . Let us unite $C$ and $D$ into single automata $E$ with $2^n + 2^k$ states. Now, any two distinguishable states of DFA with $x$ states can be distinguished with word with length at most $x - 2$, so if $A$ and $B$ are distinguishable, so states of $E$ corresponding to initial states of $A$ and $B$ are distinguishable too (with the same words), so there is word with length at most $2^n + 2^k - 2$ that distinguishes $A$ and $B$.
Best lower bound I can come up with is much lower - just $n + k - 2$, though it's enough to consider DFA to achieve it. Assume $n < k$, let $A$ have states $q_1, \ldots, q_n$ with transitions $q_1 \to_{0,1} q_1$, $q_{i - 1} \to_0 q_i$ and $q_i \to_1 q_{i - 1}$ for $i \leqslant n$ and $q_n \to_0 q_n$. Let $B$ have states $p_1, \ldots, p_k$ with transitions $p_1 \to_{0,1} p_1$, $p_{i - 1} \to_0 p_i$ for $i < k$, p_{i} \to_1 p_{i - 1}$ for $i \leqslant n$, $p_i \to p_{n - 1}$ for $n < i < k$ and $p_k \to_{0,1} p_k$. Then $A$ accepts string $0^{k - 1} 1^{n - 1}$, but $B$ rejects it, while they agree on any shorter string.
The gap between $n + k - 2$ and $2^n + 2^k - 2$ is quite significant, but for now I have no idea how to decrease it.