11
$\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$
  • $\begingroup$ Write "This automaton is...." or "These automata are....". (I fixed this in the question.) $\endgroup$ – Michael Hardy Mar 26 '13 at 3:24
11
$\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$
  • 1
    $\begingroup$ Can a finite automata have no accept states at all? $\endgroup$ – user68486 Mar 25 '13 at 22:40
  • 2
    $\begingroup$ @user68486: Yes, it can: the set of acceptor states can be any subset of the set of states. $\endgroup$ – Brian M. Scott Mar 25 '13 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 '17 at 9:24
  • $\begingroup$ for a moment I felt we shouldnt need any state (invisible FA :p)...seems thats not allowed... $\endgroup$ – anir Dec 23 '17 at 15:57
6
$\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$
1
$\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$
  • $\begingroup$ You've just said "accept empty string" and then "does not accept anything". Can you explain it better? $\endgroup$ – JB-Franco Mar 15 '17 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 '17 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 '17 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$ – Benjamin Cosman May 29 '17 at 16:13
  • $\begingroup$ @BenjaminCosman, answer me one thing, what do you mean by empty string? $\endgroup$ – lU5er May 30 '17 at 17:25

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.