1,644 views
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

is it 16?
what does designated initial state means ?
intial state can be chosen in only one way.
means if we select A as initial state in DFA1 then in DFA 2 also A will be the initial state ?
Initial state has been already defined and that initial state can accept the empty language

We should deal this type of questions using State transistion table

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

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

@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

1
304 views