Finite automaton that recognizes the empty language $\emptyset$

42.9k Views Asked by At

Since the language $L = \emptyset$ is regular, there must be a finite automaton that recognizes it. However, I'm not exactly sure how one would be constructed. I feel like the answer is trivial. Can someone help me out?

2

There are 2 best solutions below

5
On

One state, non-accepting, and no transitions. (That’s an NFA; if you want a DFA, have one transition from the state to itself for each letter of whatever alphabet is specified.)

0
On

You have only one state $s$ that is initial, but not accepting with loops $s \overset{\alpha}{\rightarrow} s$ for any letter $\alpha \in \Sigma$ (with non-deterministic automaton you can even skip the loops, i.e. the transition relation would be empty).

I hope this helps ;-)