I came across problem asking for possilble number of DFAs for a given number of states and alphabet. I started guessing if we can find possible number different automatas for given number of states, input alphabet and stack alphabet etc.
Given,
$Q$ is set of states
$Σ$ is input alphabet
$Γ$ is stack alphabet for PDAs and tape alphabet for TMs
$L$ means move head to left in TM
$R$ means move head to right in TM
$ϵ$ is empty symbol
I came up with following table:
First $Q$ in each cell of "Possible number of machines" column is possible number of start states. Last $2^Q$ is possible combinations of final states. And remaining middle part is number of transition. combinations. Also I have used the symbols directly to denote number of elements in each set. For example, $Q$ is set of states, but I used $Q$ to denote number of states.
Am I correct with these counts?
PS: this is combinatorial problem in the context of automata theory.
