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.

$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:

enter image description here

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.