Deterministic/non-deterministic state system mapping

Question

I read in a book on non-deterministic mapping there is mapping from Q*∑ to 2^Q for M=(Q,∑,trans,q₀,F) where Q is a set of states. But I am not able to understand how it's 2^Q; if there are 3 states a, b, c, how does it map to 8 states?

Answer 1

I always found that the easiest way to think about these (since the set of states is finite) is as having each of those subsets be an encoding of a base-2 number that ranges from 0 (all bits zero) to 2^|Q|-1 (all bits one), where there are as many bits in the number as there are members in the state set, Q. Then, you can just take one of these numbers and map it into a subset by using whether a particular bit in the number is set. Easy!

Here's a worked example where Q = {a,b,c}. In this case, |Q| is 3 (there are three elements) and so 2³ is 8. That means we get this if we say that the leading bit is for element a, the next bit is for b, and the trailing bit for c:

• 0 = 000 = {}
• 1 = 001 = {c}
• 2 = 010 = {b}
• 3 = 011 = {b,c}
• 4 = 100 = {a}
• 5 = 101 = {a,c}
• 6 = 110 = {a,b}
• 7 = 111 = {a,b,c}

See? That initial three states has been transformed into 8, and we have a natural numbering of them that we could use to create the labels of those states if we chose.

Now, to the interpretations of this within a non-deterministic context. Basically, the non-determinism means that we're uncertain about what state we're in. We represent this by using a pseudo-state that is the set of “real” states that we might be in; if we have total non-determinism then we are in the pseudo-state where all real-states are possible (i.e., {a,b,c}) whereas the pseudo-state where no real-states are possible (i.e., {}) is the converse (and really ought to be impossible to reach in the transition system). In a real system, you're usually not dealing with either of those extremes.

The logic of how you convert the deterministic transition system into a non-deterministic one is rather more complex than I want to go into here. (I had to read a substantial PhD thesis to learn it so it's definitely more than an SO answer's worth!)

Answer 2

2^Q means the set of all subsets of Q. For each state q and each letter x from sigma, there is a subset of Q states to which you can go from q with letter x. So yeah, if there are three states abc the set 2^Q consists of 8 elements {{}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}. It doesn't map to 8 states, it maps to one of these 8 sets. HTH