How many different finite automata are there that have 3 states $q_0$, $q_1$ and $q_3$, have an alphabet of size 2, and where $q_0$ is starting state?

  • 2
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Mar 12 '16 at 20:20
  • $\begingroup$ I have taken liberty of replacing $x,y$ and $z$ as $q_0, q_1$ and $q_2$. $\endgroup$ – Shreesh Mar 13 '16 at 13:32
  • $\begingroup$ @Shreesh Why? It doesn't matter what the states are called and $x$, $y$ and $z$ are easier to type. $\endgroup$ – David Richerby Mar 13 '16 at 23:28
  • $\begingroup$ What you are saying is true! Just wanted to stick to convention that $q_0$ is the start state in my answer. But if you say, we can rename it $x$, $y$ and $z$, and I will change my answer. At least OP will be happy. $\endgroup$ – Shreesh Mar 14 '16 at 12:05

Total number of distinct transition functions from $Q \times \Sigma \rightarrow Q$ is $3^6 = 729$. This is because $Q \times \Sigma $ has $|Q| \times |\Sigma| = 3 \times 2 = 6$ elements, and $|Q| = 3$. Every one of $6$ elements has $3$ choice for transition.

Even if there are 3 different choice of start state, that will not give us different automata, as these automata are already counted in 729 different automata with renumbering of states. So let us assume $q_0$ is the start state. Now $q_0$ is always reachable. We will remove those automata where some of the states are reachable (because we can compute these numbers easily, that is why, otherwise if we are not interested in that, we can straight away have $3^6 \times 2^3 = 5832$ distinct automata).

Number of distinct transition functions where 2 states are unreachable = $1^2.3^4 = 81$

Number of distinct transition functions where $q_1$ state is unreachable = $2^4.3^2 = 144$

Number of distinct transition functions where $q_2$ state is unreachable = $2^4.3^2 = 144$

Number of distinct transition functions where every state is reachable = $729 - 2\times144 + 81 = 522$.

Now let us count different final states.

3 final states = $522$ different automata (though language is same, however we are counting different automata, language being same is irrelevant).

1 final state = $522$ ($q_0$ final) + 522 ($q_1$ final) = $1044$ ($q_2$ final state is counted in $q_1$ final state, as it will just be renaming of state $q_1$).

2 final states = $522$ ($q_0$ and $q_1$ final states) + $522$ ($q_1$ and $q_2$ final states) = $1044$ (again we won't count $q_0$ and $q_2$ as final states).

0 final states = $522$ (perfectly valid different automate, and again languages are all same).

So total number of distinct automata is $522 + 1044 + 1044 + 522 = 3132$.

As an added note, the case of all possible two state automata is also interesting, with any alphabet size. The interesting two cases of FA will be as following:

2 state finite automata

In the automata above, $S$ is the set of all "Set" transition symbols, $R$ is the set of all "Reset" transition symbols, $T$ is the set of all "Toggle" transition symbols, and $U$ is the set of all "Unchanged" transition symbols. We set two automata depending on whether we want set condition or reset condition to be the final state. The corresponding regular expressions are

$(R+U)^*(S+T)((S+U)+(R+T)(R+U)^*(S+T))^*$ for first automata, and,
$((R+U)+(S+T)(S+U)^*(R+T))^*$ for second automata.

It is difficult to do such neat analysis for 3-state automata mainly because there will be 3^3=27 different classes of transition symbols.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.