3
$\begingroup$

So I was watching this video https://www.youtube.com/watch?v=ZjjAbFxjxLQ and the guy was explaining why the top automaton is NFA (because the initial state doesn't know what to do if the input string begins with b) and the bottom is DFA (because the initial state points to a 'dead state' if the input string begins with b): enter image description here Okay, fair enough.

But when I went on this Automaton simulator and it generated an example of a DFA for me, I got confused because its the same as the NFA example above:

enter image description here

It doesn't have an option for when the input string begins with b. So what's going on?

$\endgroup$
3
  • 1
    $\begingroup$ I think the simulator implicitly assumes that the automata goes to trap state in case input transition isn't specified. It seems the simulator is explicit in not allowing the $\epsilon$-transitions in DFA but doesn't restrict when every input transition isn't specified. So the simulator isn't precise. Follow what the guy said in the video and you'll be fine :) $\endgroup$
    – Jamāl
    Dec 26, 2020 at 23:05
  • $\begingroup$ Test the string "B" on it and you'll see that it gets rejected which means the simulator does indeed internally go to dead state on unspecified inputs. $\endgroup$
    – Jamāl
    Dec 26, 2020 at 23:10
  • $\begingroup$ I don't see any non-determinism in either of those. The first automaton simply rejects input if it starts with b. $\endgroup$
    – IS4
    Dec 27, 2020 at 23:38

2 Answers 2

8
$\begingroup$

Some people in the literature (very few actually) do not consider missing transitions as nondeterminism, and given a DFA, they allow themselves to remove all transitions that lead to states from which we cannot reach an accepting state. The reason for that is technical, as sometimes it may simplify proofs a bit. Or it could be a matter of taste.

Intuitively, allowing missing transitions is justified as nondeterminism, or guessing occurs only when we have a choice, that is, when we have at least two transitions $\langle q, \sigma, s_1 \rangle$ and $\langle q, \sigma, s_2 \rangle$, going out from the same state $q$, and are labeled with the same letter $\sigma$. So, DFAs with missing transitions, or more accurately NFAs such that for every state $q$, and letter $\sigma$, it holds that $|\delta(q, \sigma)|\leq 1$, are considered deterministic in the sense that they have at most one run on a given input word.

The most common formal definition of a DFA does not allow missing transitions. Please note that it does not really matter to which definition you stick as long as you're consistent with it. Also, given a DFA, it is easy to remove all transitions leading to a state from which we cannot reach an accepting state (because detecting states that do not lead to an accepting state can be done in polynomial time), and this does not affect the automaton's language. Conversely, given an automaton with missing transitions, you can direct all missing transitions to a rejecting sink which is a rejecting state with a self loop labeled with every letter.

$\endgroup$
1
  • $\begingroup$ MIssing transitions are deterministic if you define what to do when they happen somewhere. If you don't, well then it's undefined. Which is a kind of nondeterministic. $\endgroup$ Dec 28, 2020 at 7:27
6
$\begingroup$

Bader Abu Radi is right. In short, there are unfortunately competing definitions used by different people on this matter:

  1. According to the most common definition, the YouTube video is right: the missing transition for strings starting with b means that the top machine is an NFA, and not a DFA.

  2. But the Automaton simulator you used has a different definition, which allows missing transitions. In case of a missing transition, if you use this definition, the machine is said to not accept.

The difference between definitions (1) and (2) is minor: any valid DFA by definition (1) is a valid DFA by definition (2), and any valid DFA by definition (2) can be transformed into a valid DFA by definition (1) by adding just one additional state.

$\endgroup$
3
  • $\begingroup$ So, for 1. input symbols alphabet is the same for all states, but for 2. alphabet depends on current state of automaton. $\endgroup$
    – user28434
    Dec 27, 2020 at 8:27
  • $\begingroup$ @user28434 You can think of it that way if you like. If the input symbol is not in the input alphabet at a current state, the machine should be thought of as rejecting. $\endgroup$
    – 6005
    Dec 27, 2020 at 16:21
  • 5
    $\begingroup$ In the late '80's I was taught that 2) was a preffered shorthand for 1). Those extra arrows to black holes states are technically there, but are clutter. Draw them for your 1st DFA homework, but never again. $\endgroup$ Dec 27, 2020 at 18:43

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.