The Gateway to Computer Science Excellence
0 votes
56 views
how many Dfa's exists with two states over input alphabet {0,1}?

a) 16

b) 26

c) 32

d) 64
in Theory of Computation by (69 points) | 56 views
0

64

state 1 - may act as final/initial  2

state 2 - may act as final/initial  2

each state - on input 0 can have 2 transitions  and on input 1  can have 2 transitions  = 2*2*2*2 = 16

=  2*2*16 

+1

@manisha11 you are correct. Add it as answer.

1 Answer

+1 vote

64

state 1 - may act as final/initial  2

state 2 - may act as final/initial  2

each state - on input 0 can have 2 transitions  and on input 1  can have 2 transitions  = 2*2*2*2 = 16

=  2*2*16 

by Active (2.3k 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,737 questions
57,292 answers
198,230 comments
104,911 users