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$
3
  • 5
    $\begingroup$ Yes. Some answers are just that simple. $\endgroup$ May 1, 2015 at 2:30
  • $\begingroup$ it is not a transducer then. $\endgroup$ May 1, 2015 at 17:36
  • $\begingroup$ @GrijeshChauhan Where in the question did you find the term "transducer"? $\endgroup$
    – Raphael
    May 20, 2015 at 7:43

2 Answers 2

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
  • 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$ May 1, 2015 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, 2015 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 and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.