Let $L \subseteq {0, 1}^{*}$ be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted by a minimal DFA with k states?

Open in App

Solution

If L is accepted by a min DFA with k states, by exchanging final and non-final states, we can make a minimal DFA with k states which accepts ${0, 1}^{*} - L = ¯ ¯¯ ¯ L .$

So, option (a) is true.

Suggest Corrections

Similar questions

F o r a g i v e n l a n g u a g e L o v e r (0, 1) * w e d e f i n e t h e o p e r a t i o n i n i t (L) a s . i n i t (L) = (μ μ ρ \in L f o r s o m e ν i n (0, 1} *} L e t L_{1} = (ω ω \in (0, 1) * n_{0} (ω) = n_{1} (ω)} . L e t X d e n o t e t h e l a n g u a g e a c c e p t e d b y i n i t (L_{1}) . T h e n t h e n u m b e r o f s t a t e s i n t h e m i n i m a l D F A o f X i s e q u a l t o_____.

L ((11^{*} 0 + 0) (0 + 1)^{*} 0^{*} 1^{*})

{0, 1}

Join BYJU'S Learning Program