8
$\begingroup$

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?

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

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – David Richerby May 1 '15 at 10:31
  • 1
    $\begingroup$ @david-richerby I perfectly know this. I just mentioned that this result matches the standard definition that is given in standard courses. $\endgroup$ – J.-E. Pin May 1 '15 at 10:52
7
$\begingroup$

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).

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