in Theory of Computation
292 views
2 votes
2 votes
How many possible finite automatas with three initial states x,y,z where x is always initial state over alphabet a and b??
in Theory of Computation
292 views

1 Answer

3 votes
3 votes
Best answer

States = x, y, z  input alphabet = (a, b)

Initial state = x

(x,a) = 3   ( In state x, on input a, transition can be either to x or y or z, 3 possibilities.
(x,b) = 3

(y,a) = 3
(y,b) = 3

(z,a) = 3
(z,b) = 3

total possible DFAs = 3^6 = 729
now we have to choose final state, there are three states and final states is a subset of Q
hence there can be upto 8 final states.

Total DFAs = 729*8 =5832

edited

2 Comments

what should i check?
0
0