Does every minimal DFA contain only one finite state?

Question

I was wondering if there exist minimal deterministic finite automaton that have more than one finite state. Can one proof that by proofing that there exists a non-minimal DFA which, minimized, still has more than one finite state? Maybe with the algorithm one learns in dira/resy 1?

Answer 1

The minimal automaton of an automaton is uniquely determined. Its states describe certain equivalence relations on the words that are accepted. It may have any number of states, so that there are certainly minimal automata having more than one state. 

For example, the automaton given on the left hand side below has six states (initial state is s0 and accepting states are s2,s3,s4). Its minimal automaton is given on the right hand side and as can be seen, it has three states. 

State s5 accepts no words (since there is no path ending in an accepting state), states s2,s3,s4 accept all words a* (since these remain in the accepting states s2,s3,s4), and s0,s1 accept words a*ba*, i.e., all words where b occurs exactly once. After a second occurrence of b, we enter state s5 from where the word cannot be accepted anymore.

Comments

Thank you for your answer.

That a minimal automaton might have more than one state is very clear to me, the question I'm asking is wether a minimal automaton may have more than one **accepting** state. I accidently wrote finite instead of final in my question I guess.

Maybe you can consider my question again with "accepting" instead of "finite".

Answer 2

Here is a minimal automaton that has two accepting states s1 and s2:

Answer 3

Maybe a concrete language also helps,

Consider the language L= {a^{3k}} U {a^{5k}}, this is the union of two regular languages and thus also regular.  Since L is regular, there exists a minimal DFA accepting it. Let M be such an automaton, with starting state S and only accepting state E.

Consider the words u=aaa and v=aaaaa which are both in L and accepting in M. These two words end up in the state E in S. We have δ*(u,S)= δ*(v,S). 

Consider now x:=u*aaa and y:=v*aaa, clearly x is in L and y is not. If M was accepting we need to have δ*(x,S)=E . But  δ*(x,S)= δ*( aaa,δ*(u,S))= δ*(aaa, δ*(v,S))=δ*(y,S) , which means y is accepting and we get a contradiction.

Comments

That is a very nice example! Bytheway, the uniquely defined minimal automaton for that language consists of a ring of 15 states and is as follows:

inputs a;
init 0;
transitions
    (0,a,1); (1,a,2); (2,a,3); (3,a,4); (4,a,5); (5,a,6); (6,a,7); (7,a,8); (8,a,9);
    (9,a,10); (10,a,11); (11,a,12); (12,a,13); (13,a,14); (14,a,0);
accept 0,3,5,6,9,10,12;

As can be seen, there are many accepting states which are also requires to determine the multiples of 3 and 5 up to their lcm.