Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
The original nondeterministic FSA I have is:
After converting this to a DFA I get:
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?
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.
