# Transition function of non deterministic pushdown automata

I was reading book on Automata Theory by Peter Linz.

He gives transition function of the non deterministic finite automata as follows:

$$\delta:Q\times (\Sigma\cup\{\lambda\})\rightarrow 2^Q$$

But the transition function of non deterministic pushdown automata is given as:

$$\delta:Q\times(\Sigma\cup\{\lambda\})\times\Gamma\rightarrow$$ set of finite subsets of $$Q\times \Gamma^*$$

I understand it talks about "finite subsets", because $$Q\times \Gamma^*$$ is infinite and can have infinite subsets, should it be $$2^{Q\times \Gamma^*}$$? That is, should the transition function be:

$$\delta:Q\times(\Sigma\cup\{\lambda\})\times\Gamma\rightarrow$$ set of finite subsets of $$2^{Q\times \Gamma^*}$$

PS: $$Q$$ is set of states in automata, $$\Sigma$$ is an alphabet, $$\lambda$$ is empty symbol, $$\Gamma$$ is stack alphabet

• "$Q$ is number of states in automata, $\Sigma$ is size of alphabet" -- Is that really what the author wrote? So for the NDFA we take the union of an integer with a set containing one string, multiply another integer by the result, and the result of that not only is defined but is the domain of a transition function? – David K Nov 12 '19 at 13:04
• @davidk Q is of course the set of states. – MJD Nov 12 '19 at 14:56
• @DavidK sorry to put words "number" and "size" there. I was trying to figure out number of different possible automata for given alphabet, inputs and states. So I revisited transition function and got this doubt. In the hurry I put those words. – anir Nov 12 '19 at 15:07
• @MJD I guessed as much. The point really was just that correct writing matters. – David K Nov 12 '19 at 21:46
• A more helpful way to put it would have been "I think you meant to say that $Q$ is the set of states, not the number if states. Is that right?" – MJD Nov 12 '19 at 21:49

$$2^S$$ is the set of all subsets of $$S$$, not only the finite ones but the infinite ones also. If $$S$$ is finite, there are no infinite subsets, and “$$2^S$$” means the same as "finite subsets of $$S$$”.
But if $$S$$ is infinite, $$2^S$$ includes some infinite subsets also. Then “Finite subsets of $$S$$” means something different.