0
$\begingroup$

It's a pretty basic question, but I couldn't find an explicit answer in the book which I'm using, also when searching for it - I didn't find a reliable reference.

Correct me if I'm wrong but for two DFA's, $A , A'$ -given that $L(A) = L(A')$ doesn't mean that the DFA's are equivalent, so what are the (sufficient and necessary) conditions under which $A$ and $A'$ are equivalent? The closest I found was a claim states that in case $\bigcup_{q\in Q} L(q) \neq \bigcup_{q'\in Q'}L(q')$ (when $L(q) = \{w\in\Sigma^* : \hat{\delta}(q_0,w) =q \})$ then $A, A'$ are not equivalent.

Improve this question
$\endgroup$
1
  • 4
    $\begingroup$ By definition, two automata are equivalent if they accept the same language. $\endgroup$ – Yuval Filmus Sep 6 '18 at 5:45
3
$\begingroup$

As commented, they are equal when they accept the same language.

In practice:

Every NFA has one (1) minimized DFA, which is unique. If two minimized DFA are equal, the corresponding NFA's must also be equal.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.