Let M and N be minimal DFAs and minimal NFAs respectively , such that M has $K_{1}$ staes and N has $K_{2}$ states respectively for the same language L. Then which of the following is always correct ?

K_{1} \geq K_{2}

Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses

K_{2} \geq K_{1}

No worries! We‘ve got your back. Try BYJU‘S free classes today!

K_{1} > K_{2}

No worries! We‘ve got your back. Try BYJU‘S free classes today!

K_{1} < K_{2}

No worries! We‘ve got your back. Try BYJU‘S free classes today!

Open in App

Solution

The correct option is A $K_{1} \geq K_{2}$
(b)
Assume n represent number of state
$n (N F A) \leq n (D F A)$ for a given language L.
Hence $K_{1} \geq K_{2}$ So, Option (b) is correct .

Suggest Corrections

Similar questions

L (M) \cap L (N)

L \subseteq {0, 1}^{*}

L (M) \cup L (M^{'}) = Σ^{*}

L (M) \cap L (M^{'}) = ϕ

Join BYJU'S Learning Program