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)={\sum }^{\ast }$
$II.L\left(M\right)\cap L\left(M^{\prime }\right)=\varphi$
What is the validity of the above statements with respect to DFA's and NFA's.

• A. I and II always hold for DFA
• B. None of these
• C. I and II hold for both DFA and 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

$\text{I and II always hold for DFA, as L(M') is same as}\left[L\right(M){]}^{\prime }\varphi .$
However, the same is not the true for NFA.