The Gateway to Computer Science Excellence
0 votes
171 views
Total number of DFA possible with 2 states q0 → start and non-final, q1 → final
over Ʃ = {a,b} is
(a) 16                 (b) 32
(c) 48                 (d) 64
in Theory of Computation by (169 points) | 171 views

2 Answers

+3 votes
Best answer
On every state it has two inputs , so each input can go to one of the two states. So for every state its arrows (->) have four possible combinations. Similarly on second state it also has four combinations.of arrows emerging from it. So i think its 16.
by (377 points)
selected by
0 votes
I think if we have.

N is the number of states

S is the alphabet symbols

Then total dfa possible is (choice for initial state) * (choice for final state) *(choice for transition function)

1*1*(N^(N*S))

2^(2*2)

= 16
by (61 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,157 answers
193,767 comments
93,753 users