patternModerate
Why is this automaton considered DFA?
Viewed 0 times
thisdfawhyconsideredautomaton
Problem
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):
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:
It doesn't have an option for when the input string begins with b. So what's going on?
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:
It doesn't have an option for when the input string begins with b. So what's going on?
Solution
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 not justified as nondeterminism, or guessing occurs only when we have a choice, that is, when we have at least two different 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.
Intuitively, allowing missing transitions is not justified as nondeterminism, or guessing occurs only when we have a choice, that is, when we have at least two different 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.
Context
StackExchange Computer Science Q#133701, answer score: 10
Revisions (0)
No revisions yet.