retagged by
2,312 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
retagged by

2 Answers

3 votes
3 votes

We should deal this type of questions using State transistion table

2 votes
2 votes

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

Related questions

2 votes
2 votes
1 answer
1
Hirak asked May 22, 2019
973 views
Find the no. of DFA’s that can be constructed over the alphabet Σ with 5 symbols, and with 10 states.(a) $2^5$$^0$ × $50^5$ (b) $2^1$$^0$ × $10^5$$^0$(c) $2^5$ × ...
0 votes
0 votes
1 answer
2
3 votes
3 votes
3 answers
3
Hirak asked May 22, 2019
1,355 views
How many $2$ state DFA’s with the designated initial state can be constructed over the alphabet over the alphabet $\sum = \{a, b\}$ that accept universal language?$4$$1...