I haven't taken any discrete maths, therefore im trying to understand the syntaxes here $${\displaystyle \delta :Q\times (\Sigma )\rightarrow 2^Q \rightarrow{\mathcal {P}}(Q)}$$ So, cartesian product of set of states with input set results into $2^Q$, which is said to be set of all possible subsets of Q. But how does $2^Q$ becomes a set? Doesn't $2^Q$ represent the number of all possible states?

Also, do we call transition function just one time for all states or does it loop? Can anyone explain what transition do step by step?


1 Answer 1


$\delta$ is the transition function. It takes two arguments - the current state and a letter in the input alphabet - and its output is a subset of the states. This should contrast with your idea of a DFA, where the output is always a single state.

Try thinking about it this way: the transition function takes your current state and an input letter and returns a subset of $Q$, which could also be described as a binary number with $|Q|$ bits, each bit $i$ indicating whether state $i$ in or out of the subset.

Now, $\mathcal{P}(Q)$, the power set of $Q$, is defined to be the set of all subsets of $Q$. It also has a natural expression as the binary numbers with $|Q|$ bits or the functions from $Q$ to the set $\{0,1\}$. Note that the size of all of these is the number $2^{|Q|}$.

The last bit you're missing is that set theorists can construct the natural numbers by defining $2=\{0,1\}$. This may feel weird, but it's a useful shorthand here. Also, the set $A^B$ is defined to be the set of all functions from $B$ to $A$. Now, you can see the $2^Q$ in the definition of $\delta$ isn't a number at all, it's the set of functions from $Q$ to $2=\{0,1\}$, which is also naturally the power set of $Q$.

So, the domain of $\delta$ is $Q\times\Sigma$ and its range is $2^Q$ which is set-theoretically isomorphic to $\mathcal{P}(Q)$.

And you can't chain the transition function directly because it takes a state, not a set of states as input, but you can generalise it by defining $$\hat{\delta}(\hat{q},s) = \cup{\{\delta(q.s):q\in\hat{q}\}}$$ and then you can start at $\{q_0\}$ (rather than the state $q_0$) and apply $\hat{\delta}$ iteratively as you loop through your input word.

  • $\begingroup$ So, correct me if I'm wrong. $2^Q$ means, set of all subsets of Q over {0,1}, and it is the codomain of the function also it is the special representation. If the alphabet was {a,b,c} then we could have called it $3^Q$. For each qi and ni there is a subset of Q including epsilon, right? $\endgroup$
    – mark
    Mar 3 at 10:11
  • $\begingroup$ and, The extended transition function handles strings with looping over them $\endgroup$
    – mark
    Mar 3 at 10:29
  • $\begingroup$ No, the 2 has nothing to do with the alphabet $\Sigma$, it's about the Boolean true/false of whether each state $q$ is in a given subset of $Q$. So if there are $|Q|$ elements in $Q$ there are $2^{|Q|}$ elements in the power set $\mathcal{P}(Q)$, regardless of the alphabet used, and $2^Q$ is just another representation of $\mathcal{P}(Q)$. $\endgroup$
    – IanR
    Mar 5 at 16:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .