patternModerate
What does an NFA do if there's no transition with the correct symbol?
Viewed 0 times
thenfawhatwithsymboltransitiondoescorrectthere
Problem
So I am learning about DFA and NFA, and I need some clarification for it.
DFA
NFA
My question is does NFA need a transition for every element in the alphabet? If not, then let say the alphabet is {0. 1} and I am at a state without the transition for 1, do I go to the empty state or something?
DFA
- accept empty set
- transition for every element in the alphabet
- path are deterministic
NFA
- accept the empty set and empty string
- path are not deterministic
My question is does NFA need a transition for every element in the alphabet? If not, then let say the alphabet is {0. 1} and I am at a state without the transition for 1, do I go to the empty state or something?
Solution
In a DFA, if you are in state $p$ and see an input character $c$, one of three things may happen:
For an NFA, you have more possibilities:
In either a DFA or an NFA, you don't need to have moves defined for all possible (state, character) pairs. If you're in state $p$ and there is no move defined for an input character, the machine (or that branch) halts and rejects.
Some people don't like this behavior and complete the automaton by creating what you apparently call an empty state and defining transitions to that state on those missing inputs. Once you're in that state (also known as a dead or error state), you never leave, no matter what the input is.
- You can consume that character (i.e., read it) and change to state $q$ ($q$ may be $p$ or not).
- There may not be a move defined for the pair $(p, c)$ in which case the DFA halts and rejects the input string.
- If the DFA is in a final state after having read all the input, it accepts the input, otherwise it rejects the input.
For an NFA, you have more possibilities:
- In state $p$ with input $c$ you can consume the input and change to several states $q_1, q_2, \dotsc$ .
- In state $p$ you can elect not to consume the input and change to several states $q_1, q_2, \dotsc$. This is called an epsilon move. In essence, your machine may change state without reading any input.
- As with a DFA, there may not be any move defined for the pair $(p, c)$ or $(p, \epsilon)$ in which case the NFA halts that branch of execution.
- If the NFA is in a final state in any particular branch of its execution and has consumed all the input, it accepts the input. If it hasn't reached any accept state after having read all the input, it rejects.
In either a DFA or an NFA, you don't need to have moves defined for all possible (state, character) pairs. If you're in state $p$ and there is no move defined for an input character, the machine (or that branch) halts and rejects.
Some people don't like this behavior and complete the automaton by creating what you apparently call an empty state and defining transitions to that state on those missing inputs. Once you're in that state (also known as a dead or error state), you never leave, no matter what the input is.
Context
StackExchange Computer Science Q#32431, answer score: 11
Revisions (0)
No revisions yet.