My coursework question asks me to "Draw a State Transition for the nondeterministic finite state machine (NDFSM)" from a state transition table. By following the examples in our lecture materials, I've managed to complete this, however, I have a few questions where it differs from the notes.
1) When converting the NDFSM to a DFSM, s2 produces nothing when given input "a" meaning I have nothing noted for the DFSM state S2. I presume this is allowed?
2) My State Transition Network doesn't use all the possible states (the machine never enters some states after receiving input). For example, the DFSM has 15 nodes on it, of which only 7 are drawn onto the Network Diagram. Should I draw the empty nodes as isolated ones or just leave them off entirely?
Thanks!
Drawing the digraph from the transition table is a mechanical procedure that doesn’t match the rest of your question. From the rest of your question it sounds as if what you’re actually trying to do is convert the non-deterministic machine to an equivalent deterministic one using the subset algorithm. I’ll make the further guess that the NDFSM has $4$ states. If so, your DFSM should have $2^4=16$ states, not $15$, and I suspect that the state that you’re missing is the one corresponding to $\varnothing$, the empty set of states in your NDFSM. If the state $s_2$ in the NDFSM has no $a$-transition, then the state $\{s_2\}$ in your DFSM should have an $a$-transition to $\varnothing$. And of course every transition from $\varnothing$ will be a loop back to $\varnothing$.
The answer to your second question depends on what your instructor wants. I’d omit the unreachable states, but I could imagine an instructor wanting to see them the first time or two that you go through the construction.