in Theory of Computation retagged by
1,512 views
3 votes
3 votes
How many 2 state DFA’s with designated initial state can be constructed over the alphabet Σ = {a, b} that accept empty language ϕ ?
(a) 4       (b) 16     (c) 20       (d) 24
in Theory of Computation retagged by
by
1.5k views

4 Comments

means if we select A as initial state in DFA1 then in DFA 2 also A will be the initial state ?
0
0
Initial state has been already defined and that initial state can accept the empty language
0
0

2 Answers

2 votes
2 votes

We should deal this type of questions using State transistion table

1 vote
1 vote

case1:when no final state to be chosen.

    then dfa possible=2^4=16.

case2:when X is initial state and Y is final state but unreachable from X

  then dfa possible =2^2=4

therefore in total dfa possible is =16+4=20.Ans

2 Comments

But initial state can accept the empty language means initial state is also a final state right ??
0
0

@Srken In Empty language there are no strings present right 

you are confusing between Empty language and Empty string

Dfa has initial state as final state if it accepts Empty string ϵ and not Empty Language 

0
0