0

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!

user3494322
  • 1

1 Answers1

1

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.

Brian M. Scott
  • 616,228
  • Thanks for your reply. You are correct in assuming that the NDFSM had 4 states. I have filled in the ∅ mark under (s2,a) now. On a further review of the lecture notes, step 1 for conversion says to "Create a new set of states, P, which is all possible subsets created from S (omitting the empty set)". This empty set would have been the 16th state (which would explain why I only have 15).

    I think I'll leave the unreachable states out as it would look overly complicated, since in the lecture notes he only ran through one example that happened to use all states, this situation was not covered.

     – user3494322 May 03 '15 at 11:36
  • @user3494322: You’re welcome. I’m surprised at the instruction to omit the empty set, unless your instructor is one of those who define DFSMs so as not to require a transition for every possible input out of each state. – Brian M. Scott May 03 '15 at 18:16