4
$\begingroup$

I am trying to understand how many states should be there in a Finite Automata which does not accept anything.

I thought it to be containing only one non-final state, the starting state, with all transitions going to itself.

But one of my teachers mentioned that the set of final states cannot be empty. Does that mean there will be two states states, one start state and one final state, with no transition between the two?

$\endgroup$
  • 1
    $\begingroup$ There is no such thing as "a finite automata". It's "an automaton". "Automata" is plural. $\endgroup$ – Emil Jeřábek supports Monica Oct 27 '16 at 6:52
  • 7
    $\begingroup$ Which exact definition does your teacher use? All I know admit an empty set of final states. $\endgroup$ – Raphael Oct 27 '16 at 9:49
  • $\begingroup$ cs.stackexchange.com/q/69849/755 $\endgroup$ – D.W. Feb 10 '17 at 5:47
7
$\begingroup$

The standard definition of DFA (as well as NFA) allows the set of accepting states to be empty. Indeed, otherwise the Myhill–Nerode theorem would be false. The theorem states that the number of states in a minimal DFA for $L$ equals the number of equivalence classes in the Myhill–Nerode relation for $L$. When $L = \emptyset$, this relation contains one equivalence class (consisting of all strings), and so there should be a DFA for $L$ having a single state.

Of course, you can define DFAs in any way you like, and in particular, your teacher's definition still results in the same class of regular languages. Nevertheless, the standard definition is better, for the reason stated above.

$\endgroup$
  • $\begingroup$ Of course, a minimal automaton for $\Sigma^*$ has only one state as well. $\endgroup$ – Raphael Oct 27 '16 at 11:05
3
$\begingroup$

the resulting automaton consists of one state which transitions to itself on every symbol in the input alphabet. Note that is state is non accepting. An Automaton should always have an initial state but the set of final states could be empty.

$\endgroup$
3
$\begingroup$

The finite automaton accepting nothing will contain transitions on all input symbols to itself only. Thus atleast $1$ state is necessarily required.

A language accepting nothing can be considered as complement of language accepting everything. We know that language accepting everything has only one state with that state being initial and final state.

$\endgroup$
  • 1
    $\begingroup$ Note that automata accept strings; languages contain them -- a language is just a set. $\endgroup$ – David Richerby Oct 28 '16 at 11:59
0
$\begingroup$

Maybe the solution your teacher proposed is an automaton with 2 states 1 starting and 1 final, but with 0 transitions, so technically the final transition does not accept anything.

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