1
$\begingroup$

I want to know if I want to draw up a finite state machine, say for example binary strings and I want a finite state machine that accepts only one kind of binary string e.g: 0110. Do I, for each state have to account for another symbol of the binary language being read during transition. Like for the first transition, this will be caused by 0 being read, but what if a 1 is read...do I have to implement a trap state or do I just not account for the fact that a 1 could be entered 1st?

$\endgroup$
  • $\begingroup$ If you only want to accept 0110, then yes, you need a dead state or trap state. $\endgroup$ – Ayush Agarwal Oct 9 '16 at 12:33
5
$\begingroup$

Your question isn't entirely clear but it's easy enough to just list all the possible answers that could arise, depending on exactly what you mean.

If you're asking about nondeterministic finite automata (NFAs) then you don't need to account for every symbol. The rule is that, if you're in a state and you encounter a symbol that has no transition, then that branch of the computation rejects immediately.

If you're asking about deterministic finite automata (DFAs), then it depends on exactly what definition you're using. The classical definition (e.g., in Sipser) is that every state must have exactly one transition for each possible symbol. In that interpretation, you need a trap state, since you must specify what happens for every possible symbol you could read. Other authors, though, say that each state of a DFA has at most one transition for each symbol. In that case, you don't need a trap state: as with an NFA, if you read a symbol that has no transition, you reject.

$\endgroup$

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.