3
$\begingroup$

How many DFA's exist with two states over the input alphabet $\{0,1\}$?


My attempt :

Input set is given. So, we have 3 parts of DFA which we can change:

  1. Start state
  2. Transition Function
  3. Final state

Start state can be chosen as any one among 2 in 2 ways.

Transition function is from $Q \times Z$ to $Q$, where $Q$ is the set of states and $Z$ is the alphabet. $|Q| = 2$, $|Z| = 2$. So, number of possible transition functions $= 2^{2 \times 2} = 2^{4}$

Final state can be any subset of the set of states including the empty set. With $2$ states, we can have $2^2 = 4$ possible sub states.

Thus total number of DFAs possible :

$=2\times2^4\times4=128$.

Where total 40 DFA's are accepting empty language.

Can you explain in formal way, with a formula, please?

$\endgroup$
  • $\begingroup$ Your title and your question do not match: Two states or three states? $\endgroup$ – Lee Mosher Feb 3 '16 at 13:24
  • $\begingroup$ Sorry for typo. Thanks. $\endgroup$ – 1 0 Feb 3 '16 at 13:25
  • $\begingroup$ Your attempt seems to be very clean. What kind of formula do you wish? $\endgroup$ – J.-E. Pin Feb 3 '16 at 14:04
  • $\begingroup$ Assume, if we have $n$ states, over total input alphabet is $m$ . Then what will be total number of DFAs and how many DFAs accepted empty languages ? $\endgroup$ – 1 0 Feb 3 '16 at 14:13
  • $\begingroup$ Why don't you apply the same argument to the general case? $\endgroup$ – J.-E. Pin Feb 3 '16 at 15:09
1
$\begingroup$

Your solution looks correct, If you are looking for a formula

For $k$ states and $i$ input alphabets

$$k^{ki+1}\times 2^{k}$$

$\endgroup$
0
$\begingroup$

Sorry, but I think your solution is incorrect. If with N states an alphabet of size Z, you have N * N * Z: For each state,for each symbol in Z, there in a transition leading to one of N possible destination states. (n+1 if you allow the automaton to not be completely defined).

$\endgroup$

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.