patternMinor
Automata for empty language
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?
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.
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.