5,562 views

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

1. $L-\{01\}$
2. $L \cup \{01\}$
3. $\{0,1\}^* – L$
4. $L \cdot L$

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.

How (see the last section of the answer)

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

If $L = \{ 01\},$ then what is $L \,– \, \{ 01\}$ ?

sorry I was thinking L as L*.

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

Since they haven't explicitly mentioned not to change property, i did it..

Moreover if we go through proofs of closure properties, we have added transitions, reversed direction of transitions and lot more... So i didn't see any problem in doing that..
in option D,  L*L why this in not true??

because regular language in closed under concatination .

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

if min. DFA with ‘k’ states accepts L(m) then the just by flipping states of same min.DFA it can accept L(m)’.

As in DFA  L(m’)=L(m)’ where L(m) language accepted by the the DFA ‘m’.

so option (C) is the answer.