0
$\begingroup$

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:

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.

$\endgroup$

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.