16
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Write "This automaton is...." or "These automata are....". (I fixed this in the question.) $\endgroup$ Mar 26, 2013 at 3:24

4 Answers 4

14
$\begingroup$

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.)

$\endgroup$
5
  • 1
    $\begingroup$ Can a finite automata have no accept states at all? $\endgroup$
    – user68486
    Mar 25, 2013 at 22:40
  • 3
    $\begingroup$ @user68486: Yes, it can: the set of acceptor states can be any subset of the set of states. $\endgroup$ Mar 25, 2013 at 22:42
  • $\begingroup$ Can you please elaborate, why the NFA can have no transitions, but the DFA must have a transition for every letter in the alphabet? $\endgroup$
    – de_dust
    Oct 19, 2017 at 9:24
  • $\begingroup$ for a moment I felt we shouldnt need any state (invisible FA :p)...seems thats not allowed... $\endgroup$
    – RajS
    Dec 23, 2017 at 15:57
  • $\begingroup$ @de_dust, it's because that one definition of DFA is that there exists a delta function $\delta: Q \times \Sigma$. It means that any state must has one transition to every symbol. $\endgroup$
    – igorkf
    Oct 30, 2021 at 3:40
7
$\begingroup$

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 ;-)

$\endgroup$
2
$\begingroup$

Given language is "empty language".We have to construct a finite automata for this language.In general we consider "the construction of finite automata" as "the construction of DFA".So....{Let us assume input symbol as 'a' and 'b'}

(a)If we take one state(initial state) and don't show any transition of any input symbol over this state,then this structure will not be a DFA because in a DFA there should be a transition of all input symbol over each state. (b)If we take one state(initial state) and show the transition of both input symbol 'a' and 'b' over this state, then also this will not be a DFA because there should be a final state. (c)If we take one state(initial state) and show the transition of both input symbol 'a' and 'b' over this state,and making this state final also then this FA will not be acceptor of "empty language". (d)If we take one initial state 'A'(not making final it) showing the transition of both input symbol over 'A' itself AND taking one another state 'B'(as final)showing the transition of both input symbol over the "transion edge" from final state 'B' to initial state 'A'('B'is UNREACHABLE STATE here).Then this structure will be a DFA but not minimal DFA because in minimal DFA we remove UNREACHABLE STATE. (e)similarly we cannot take concept of dead state in construction of minimal DFA.

SO NOW THE EXACT SOLUTION IS :-

" TAKE ONE INITIAL STATE 'A'(not making final it) and ONE ANOTHER STATE 'B'(making it final) and SHOW transition of both input symbol 'a' and 'b' over both state A' and 'B'. BUT don't connect both states with any transition edge. This is the desired minimal DFA which accepts "empty language".

$\endgroup$
1
$\begingroup$

This will be the DFA

This is the DFA that iterates over (0|1)* but does not accept anything (not even empty string).

$\endgroup$
14
  • $\begingroup$ You've just said "accept empty string" and then "does not accept anything". Can you explain it better? $\endgroup$
    – JB-Franco
    Mar 15, 2017 at 22:24
  • 1
    $\begingroup$ @JB-Franco Acceptance of empty thing == not accepting anything! I think you are aware of "empty language", which means "no string", So to rephrase, "accepts empty string" == "accepts no string" == "does not accepts anything". If you still have problems, please comment. $\endgroup$
    – lu5er
    Mar 17, 2017 at 12:17
  • $\begingroup$ Thanks! - The fact you have explained in the above about DFA accepting empty string, can be related to what I have asked here: Why in a DFA the empty string distinguishes any accept state from any reject state? $\endgroup$
    – JB-Franco
    Mar 17, 2017 at 19:41
  • 1
    $\begingroup$ This answer is wrong because "accepts empty string" and "accepts no string" are not the same! The NFA with only one state and no transitions accepts no strings if the state is non-accepting, and the empty string (but no other strings) if the state is accepting. Similarly, a DFA can accept only the empty string and no others by having a start state which is accepting and then all transitions point to a non-accepting trap state like the one in this answer. $\endgroup$ May 29, 2017 at 16:13
  • $\begingroup$ @BenjaminCosman, answer me one thing, what do you mean by empty string? $\endgroup$
    – lu5er
    May 30, 2017 at 17:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .