retagged by
16,332 views
33 votes
33 votes
Is there any procedure to generalize these types of problems ?

 

Thanks in advance
retagged by

3 Answers

Best answer
55 votes
55 votes

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 3 in 3 ways.

Transition function is from Q ⨯ Z to Q, where Q is the set of states and Z is the alphabet state. |Q| = 3, |Z| = 2. So, number of possible transition functions = 3(3 * 2) = 36

Final state can be any subset of the set of states including empty set. With 3 states, we can have 23 = 8 possible sub states.

Thus total number of DFAs possible 

$= 3 \times 3^6 \times 2^3 =  17496$

For $n$ states and $m$ input alphabets we can have the formula

$$n \times n^{n m} \times 2^ n = n^{mn + 1} \times 2^n $$

In a DFA there might not be a difference if start state changes- as states are unlabeled usually. In such a case, we can divide the above by number of states giving $n^{mn} \times 2^n$ possible DFAs. 

edited by
10 votes
10 votes
.      State ↓        input →     0           1
 2         X                                3           3
 2         Y                                3           3
 2         Z                                3           3
Total no of DFA = 3*3*3*3*3*3*2*2*2
                             =  5832
No of DFA with x is starting state = 5832
No of DFA with y is starting state = 5832
No of DFA with z is starting state = 5832
Total DFA = 3*5832 = 17496

Related questions

0 votes
0 votes
0 answers
1
koushriek asked May 19, 2022
1,281 views
Examples of accepted words: 1011, 101101, 1111Example of non-accepted words: 101, 1001, 010The solution says the min-DFA contains 5 states but I could only do it in 4. Am...
4 votes
4 votes
3 answers
2
AnilGoudar asked Apr 1, 2017
3,829 views
How many 3 state DFA's can be constructed with a designated initial final state that accepts empty language over alphabet {a,b}?