in Theory of Computation retagged by
9,091 views
20 votes
20 votes

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$
in Theory of Computation retagged by
by
9.1k views

3 Answers

31 votes
31 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.

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 

edited by

4 Comments

@Deepak Poonia @Kabir5454 @Abhrajyoti00

How (see the last section of the answer)

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

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

sorry I was thinking L as L*.

I got the answer.

0
0
19 votes
19 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

4 Comments

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..
0
0
in option D,  L*L why this in not true??

because regular language in closed under concatination .
0
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

1
1
1 vote
1 vote
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.
Answer:

Related questions