0
$\begingroup$

The original nondeterministic FSA I have is:

NDFA

After converting this to a DFA I get:

DFA

If I use the Myhill-Nerode theorem on the current DFA, I get all pairs marked, so this is already minimized. But I think this is incorrect.

I want to minimize this DFA. How should I do this using the Myhill-Nerode theorem, since some of the states are merged already?

$\endgroup$
  • 2
    $\begingroup$ "I think this is incorrect." Why? $\endgroup$ – Apass.Jack Feb 14 at 4:07
  • $\begingroup$ @Apass.Jack The question asks for minimization of the DFA, so I didn't think that it would already be minimized. $\endgroup$ – Ansar Al Feb 14 at 13:20
  • $\begingroup$ "I didn't think that it would already be minimized." Why? What did you mean by "I get all pairs marked, so this is already minimized."? Why did you say "so"? $\endgroup$ – Apass.Jack Feb 14 at 14:18
1
$\begingroup$

After inputs $\epsilon$, $a$, $ab$, $abc$, $abca$ we must be in five different states because appending $b$ to one of these leads to an accept only for $abca$, appending nothing to any of the others leads to an accept only for $abc$, appending $c$ leads to an accept only for $ab$, appending $bc$ to any of the remaining only for $a$.

A bit more formally, given a string $\alpha$, we note in a 4-tuple whether $\alpha$, $\alpha b$, $\alpha c$, $\alpha bc$ are accepted. For $\alpha = \epsilon, a,ab,abc,abca$, these 4-tuples are $(0,0,0,0)$, $(0,0,0,1)$, $(0,0,1,0)$, $(1,0,0,0)$, $(1,0,0,1)$, hence all distintc. This is only possible if these $\alpha$ correspond to differnt states.

$\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.