Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

# TOC-grand test-Q14

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Let $X$ represents the number of two state DFA's possible with designated initial state accepting empty language. And $Y$ represents the number of two state NFA's possible with designated initial state accepting empty language. Find the value of $Y - X$ ?

States = $\{ X,Y\}$ , Initial state =$X$ , Alphabets = $\{0,1\}$

reshown Sep 8, 2019

DFA [ suppose inital state is A ]

case 1: no final state

no of dfa possible = 2*2*2*2=16

case 2: B as final state and no transition from A to B(from B to A possible)

no of dfa possible=2*2=4

TOTAL=16+4=20

NFA[let initial state be A]

case 1: no final state

no fo nfa possible=4*4*4*4=256

case 2: B as final state and no transition from A to B

no of nfa possible= 2*2*4*4=64

total=256+64=320

overall Y-X=320-20=300
answered Sep 8, 2019 by (9,500 points)
selected Sep 11, 2019 by
though i have done the nfa part wrong in exam . i missed 2*2 in nfa case2
300 is correct
here,why 2*2*4*4 for nfa?didnot get this.