Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I need to create a DFA for a sequential order of states e.g.
A -> B -> C -> B -> A
and so on, where 'A' is the start and finish state,
1 is a transition to the next state and 0 just loops back to the current state.
1 and 0 are the only inputs
The only way I've found I can do it in this order is by having 2 B states, Is this ok or is there another way to do this?
Ask yourself this: what do you mean by the same state? In particular, why do your two $B$ states need to be the same state and what value does that give you over treating them as two separate states?
For a more thorough answer: consider the formal definition of the DFA, which includes the transition function $\delta(Q \times \Sigma) \rightarrow Q$ ($Q$ being the set of states, $\Sigma$ being the set of input symbols). The notion of there being "duplicate" states is already invalidated by $Q$ being a set of states, but since the actual behavior of the automaton emerges from the state transition function, let's consider the implication of there being duplicate states regarding that.
Let's call the two states you've labeled $B$ by the names $b_1$ and $b_2$. Since you want them to be the same state, $b_1 = b_2$. Since $\delta$ is a function, for any $\sigma \in \Sigma$ it must therefore hold that $\delta(b_1, \sigma) = \delta(b_2, \sigma)$. In English: if $b_1$ and $b_2$ are the same state they cannot behave differently between each other wrt. the state transition function. Therefore your $B$ states must be separate states: if $\delta(B, 1) = C$ at one point, it will be that, always.
Naturally, this does not invalidate your automaton in other ways – what you want to define is probably possible, but the notion of there being multiples of the same state is incompatible with the definition of DFA, and I don't see any value in trying to fudge the formalism to make them possible either.
A DFA must have at most a single transition on a given input. In your example, being in state $B$ and reading a 1 you have two choices for the resulting state: go to $A$ or $C$. You could, though have a nondeterministic FA that would achieve this. The resulting language would consist of all strings of $1$s of even length.
