Answer : Option C.
The question is asking about Number of states in minimal DFA.
If $L$ is regular then so is $L - \{01 \}$, so is $L \cup \{01 \}$ , so is $L.L$, so is $\{0,1 \}^* – L.$
But if minimal DFA for $L$ has $k$ states then can we guarantee that minimal DFA for $L - \{01 \}$ will have $k$ states ?? can we guarantee that minimal DFA for $L \cup \{01 \}$ will have $k$ states ?? can we guarantee that minimal DFA for $L.L$ will have $k$ states ?? can we guarantee that minimal DFA for complement of $L$ will have $k$ states ??
First we will check Option C. We will prove that if minimal DFA for a regular language $L$ has $n$ states then the minimal DFA for complement of $L$ will also have $n$ states.
Video Explanation of this Proof: https://youtu.be/3szxKVVUo1A
Since $L$ is regular language, so, we have some DFA $D$ that accepts $L$.
We can describe D as following : $D(Q,Σ, δ, q_0, F)$
In this DFA $D$, If we make the accepting states be non-accepting, and make the non-accepting states be accepting, then this new automata $D’$ can be described as $D’(Q,Σ, δ, q_0, Q-F)$ (Because in $D’$, set of final states is $Q-F$) and this $D’$ has following properties :
1. $D’ $ is a DFA (Because we are not changing the transition function so for every state, on every alphabet symbol we still have exactly one transitions)
2. Since $D, D’$ have same states, same initial state, same transition function, So, on any string $w,$ both $D,D’$ will go to same state, say, $q.$ Now, we have two cases :
- if $q$ is final state in $D$ then $q$ is non-final in $D’$, So, $w \in L(D)$ and $w \notin L(D’)$
- if $q$ is non-final state in $D$ then $q$ is final in $D’$, So, $w \notin L(D)$ and $w \in L(D’)$
So, any string $w$, either it belongs to $L(D) $ or to $L(D’) $ But Not to both. So, $L(D)$ and $L(D’)$ are complement of each other.
So, the conclusion is that :
If a DFA $D$ accepts language $L$, then DFA $D’$ will accept language $L’,$ where $D’$ is constructed from $D$ by changing the final states to Non-final and vice versa.
So far we have proven that If $D$ is DFA for $L$ then $D’$ is DFA for $L’.$
Now, the second part is to prove that :
If $D$ is minimal DFA for $L$ then $D’$ is minimal DFA for $L’.$
This is easy to prove by contradiction.
Let DFA $D$ be the minimal DFA of $L$ with $n$ states in it.
For contradiction, let us assume that DFA $D’$ is Not minimal DFA for $L’ $ then it means that $L’$ has some minimal DFA $M$ in which we have less than $n$ states.
Now, we construct $M’$ by swapping final and non-final states in $M$, So, $M’$ will accept complement of $L’$ i.e. $M' $ accepts $L.$ So, now we have a DFA ($M’$) for $L$ in which we have less than $n$ states. But this is contradiction because minimal DFA for $L$ has $n$ states.
So, our assumption is false i.e. It is Not the case that DFA $D’$ is Not minimal DFA for $L’ .$
So, $D’$ is minimal DFA for $L’.$
So, we have proven that :
If a $D$ is a minimal DFA for a regular language $L$ then $D’$ is minimal DFA for $L’$.
Since $D$ and $D’$ have same number of states, so we can say that number of states in minimal DFA for regular language $L $ and number of states in minimal DFA for complement of $L$ is same.
Option A is false :
For counter example, take $L = \{ 01 \} $, minimal DFA for $L$ has $4$ states. But minimal DFA for $L – \{01 \}$ has $1$ state only.
Option B is false :
For counter example, take $L = \{ \} $, minimal DFA for $L$ has $1$ state. But minimal DFA for $L \cup \{01 \}$ has $4$ states.
Option D is false :
For counter example, take $L = \{ 0 \} $, minimal DFA for $L$ has $3$ states. But minimal DFA for $L.L$ has $4$ states.
Detailed Video Explanation: https://youtu.be/3szxKVVUo1A
