HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Automata for empty language

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
automataemptyforlanguage

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#65180, answer score: 7

Revisions (0)

No revisions yet.