-1

I was looking for definite conditions for a DFA to be universal.

So far, I've mainly found this:

A DFA is universal iff all its states (minimal states) are final.

This does not seem enough however: a DFA having a single state, which would be initial and final at the same time, will not be universal and would only accept the empty language, should there be no transitions over that state.

What is the correct/formal criterion in order for the DFA to be universal?

Rabih Melko
  • 3

1 Answers1

1

The statement "A DFA is universal iff all its states are final" is only true, if according to your definition a DFA has to be complete (which indeed is required often). But your example automaton is not complete, because it does not have transitions for all symbols from its unique state. If you add these, the automaton indeed accepts $\Sigma^*$ and is thus universal.

To be more explicit, you could formulate your condition as:

A complete DFA is universal iff all its states are final.

This makes sense, because in a complete DFA every string is processed along some path, which necessarily ends in some state; if all states are final, all strings are accepted.

Peter Leupold
  • 1,220
  • Yes, but what if we assume the stateless automaton? – Rabih Melko May 07 '19 at 10:25
  • Again you have to look at your definitions. Are automata without any state allowed at all? What is usually called "stateless" are automata with only one state. The "stateless" just refers to the fact that one does not need to pay attention to what state the automaton is in. If there is no state set in the definition, they are simply not DFAs. – Peter Leupold May 07 '19 at 10:38