GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 9

Question

The number of two state DFAs with a designated initial state and a designated final state that can be constructed over the alphabet set $\Sigma = \{0,1\}$ is _______

Comments

if initial state is also final state and state Y is non final state, why this case is not taken?

---

Both initial and final states are “designated” as mentioned in the question.

Answer 1

We can do in this way.
$$\begin{array}{ c|c|c }
\hline
 & 0 & 1 \\\hline
\rightarrow X & X\mid Y & X\mid Y \\\hline
\ast Y & X\mid Y & X\mid Y \\
 \hline
\end{array}$$
The number of DFAs $ = 2 \times 2 \times 2 \times 2 = 16.$

So, the correct answer is $16.$

Comments

sir i did not get it can anyone please elaborate

---

@vaibhav, see the diagram in the answer. “X | Y” means it can be filled with either X or Y. Means each of the 4 places can be filled with 2 things:- X or Y. So total 16

---

Designated initial and final state, they can be

1. X is Initial, X is Final
2. X is Initial, Y is Final
3. Y is Initial, Y is Final
4. Y is Initial, X is Final

for each state, we have 2 possibilities either it can go on X or Y =  $2^4$

Total Possibilities = $4*2^4 = 64$.

@Deepak Poonia sir, why we are not considering the designated initial state possibilities?

Answer 2

Here it is say designated initial and final state so they are fixed .

so we just need to calculate the transition possible.

now for dfa $Q × Σ → Q$

here Q={Q1,Q2} as defined two states.

$\sum \doteq${0,1}.

so number of function possible 2^4.

 

Q × Σ contain 4 elements .

∑ contains 2 elements.

Comments

if the “designated” word was not there then, the actual answer will be : 

     FINAL   :   START

$\begin{pmatrix} \phi\ \\X \\Y \\ X/Y \end{pmatrix}$ : $\begin{pmatrix} X\\Y\end{pmatrix}$

$2^{4}$ * (4*2) = 8 * 16 ≈ 128 DFA’s

 

Am I right @Deepak Poonia sir, @Kabir5454 bro ?

---

If the “designated” word was not there then more information would be required such as states are labeled or not, whether to find non-isomorphic designs or not etc..

---

Sir, If we take unlabeled states & we have to find non isomorphic designs only, then sir above answer & it's way is correct ?