Problem Detail: I have a finite automaton with no final/accepting states, so F is empty. How do I minimize it? I got this on a test and I didn’t know how to approach the problem because the automaton had no accepting states. Is a single initial state with all the transitions into itself the correct answer?
Asked By : crs12decoder
Answered By : J.-E. Pin
Your guess is correct and you can see it a little bit more formally as follows. Let $mathcal{A} = (Q, A, cdot, q_0, F)$ be a DFA. The Nerode congruence $sim$ on $Q$ is defined as follows: $$ p sim q text{ if and only if, for every word $u in A^*$, } p cdot u in F iff q cdot u in F $$ The set of states of the minimal automaton of $mathcal{A}$ is $Q/{sim}$. Now if $F$ is the empty set, all the states of $Q$ are $sim$-equivalent and thus $Q/{sim}$ has only one element, say $Q/{sim} = {1}$. You have no choice for the transitions and thus $1 cdot a = 1$ for each letter $a$. Finally $1$ is the initial state, but there is no final state.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/42025 Ask a Question Download Related Notes/Documents
