[Solved]: Minimize Deterministic Finite Automata with no accepting states

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