@Deepak Poonia @Kabir5454 @Abhrajyoti00

How (see the last section of the answer)

**DFA for L–{01} has 1 state only. **

Dark Mode

5,562 views

26 votes

Best answer

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.

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.

@Deepak Poonia @Kabir5454 @Abhrajyoti00

How (see the last section of the answer)

**DFA for L–{01} has 1 state only. **

0

15 votes

c is the correct option .

$\{0,1\}^{*}-L$ = complement of language L.

Since we have minimal dfa with k states for given language L,

we can just flip final and non final states to get the dfa which accepts complement of L without changing number of states

$\{0,1\}^{*}-L$ = complement of language L.

Since we have minimal dfa with k states for given language L,

we can just flip final and non final states to get the dfa which accepts complement of L without changing number of states

0

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 ??

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.

Option C is true and proof can be found in below link :

https://gateoverflow.in/357531/gate-cse-2021-set-2-question-9?show=358978#a358978

0