Question

Let M be a finite automata. Let M' denote the machine obtained by interchanging the final and non final states in the machine M.

I. $L\left(M\right)\cup L\left(M^{\prime }\right)={\Sigma }^{\ast }$
II. $L\left(M\right)\cap L\left(M^{\prime }\right)=\varphi$

What is the validity of the above statements with respect to DFAs and NFAs?

• A. I and II always hold for DFA, but may or may not hold for NFA
• B. None of these
• C. I and II always hold for both DFA as well as NFA
• D. I and II always hold for DFA but never hold for NFA

Answer 1

The correct option is A I and II always hold for DFA, but may or may not hold for NFA

I and II always holds for DFA, as L(M') is same as [L(M)]'. However the same is not true for NFA.