# Minimize Deterministic Finite Automata with no accepting states

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?

• Yes. Some answers are just that simple. – Luke Mathieson May 1 '15 at 2:30
• it is not a transducer then. – Grijesh Chauhan May 1 '15 at 17:36
• @GrijeshChauhan Where in the question did you find the term "transducer"? – Raphael May 20 '15 at 7:43

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.
• There's absolutely no need to use the Nerode congruence to prove that a one-state automaton is minimal for the empty language. It's quite formal enough to say that an automaton with no accepting states accepts $\emptyset$ and that a one-state automaton that accepts a particular language must be minimal because every automaton must have at least one state. – David Richerby May 1 '15 at 10:31
A finite automaton without end states denotes the language L = $\emptyset$ . To minimize a DFA we minimize the number of states and the denoted language must be the same. By definition of DFA we must have an initial state $q_0$ so $| Q | \geq 1$ and as you say we need to include the transition function with all transition into $q_0$ (because creating dead states is counterproductive).