Ace Academy Question Bank: Automata

Question

Find the no. of DFA’s that can be constructed over the alphabet Σ with 5 symbols, and with 10 states.

(a) $2^5$$^0$ × $50^5$   
(b) $2^1$$^0$ × $10^5$$^0$
(c) $2^5$ × $10^5$$^0$
(d) $2^5$$^0$ × $50^5$

Answer 1

Ans:(b)

Explanation: The DFA's are defined by the set of final states and the transitions. (Assuming there is a designated starting state).

We know transition of DFA's are of the form $\delta(q_i,a)=q_j$. Now given there are 10 states and 5 symbols. $\therefore |Q\times \Sigma|=5\times 10=50$. Now each of these two-tuples can map to any of the 10 states . Therefore there are $10^{50}$ possibilities.

Now the set of final states can be a subset of the 10 states. Therefore total possibilities=$2^{10}$.

Hence, the required answer is $2^{10}\times10^{50}$

Comments

Thanks.. :)

---

2^10 × 10^51 should have been more apt right? as we are given no fixed initial state...!

---

Yes you are right.

---

It will not accept empty language, right??

---

It might accept an empty language, since there is also a provision that none of the states are final states.

---

So, $10^{50}$ confirmed.

But it will not all cases

So, need individual calculation

right??

---

@Arkaprava

whatever answer u given , it is for all final state

right??

---

Yes,there can be several different cases. Suppose that last state is final state. Now all transitions are of the form
$\delta(q_i,a)=q_0,$ $\forall$ $q_i $ $\epsilon$ $Q$,$\forall$ $a$  $\epsilon$ $\Sigma$ where $q_0$ is the start state. Therefore this will also accept an empty language. So, there can be a very large number of cases.

---

@srestha My answer comprises of all the possible dfa's, 

---

Is it not

$10^{50}+^{10}\textrm{C}_{1}.1^{5}.10^{45}+^{10}\textrm{C}_{2}.2^{10}.10^{40}+^{10}\textrm{C}_{3}.3^{15}.10^{40}+..........$ like that??

In ur ans , there is no transition for non final state

---

How are you getting this quantity?

---

transition through nonfinal state also required

rt??

---

Yes but it is selected already. There are 50 ordered pairs of states and alphabets. There are 10 possible states which each pair can map  for every $(2^n)$ possible set of final states.

---

yes, final state to nonfinal transition is there.

But nonfinal to nonfinal. transition not there.

---

See we don't have to account seperately for non final to final and non final to non final, as we are already selecting the set of final states for each of which there are $10^{50} $ transitions.

 

@Arjun sir correct me if I'm wrong.

---

nonfinal to nonfinal transition will be there, as it accepts empty language

---

Now the set of final states can be a subset of the 10 states. Therefore total possibilities=2^10

Please explain this line

---

Given a set has $n$ elements. How many possible subsets does it have ?

---

$2^n$.

Read about the power set.