GATE CSE 2012 | Question: 12

Question

What is the complement of the language accepted by the NFA shown below?
Assume $\Sigma = \{a\}$ and $\epsilon$ is the empty string.

• A. $\phi$
• B. $\{\epsilon\}$
• C. $a^*$
• D. $\{a , \epsilon\}$

Comments

What will be the NFA for the complement of the lang?

All state transition arrows will be reversed and non-final states will be final and vice-versa. Is it correct?

---

arrows will not be reversed.....

---

Assume $\sum=\{a\}$ and $\epsilon$ is the empty string. 

      $L=\left\{a^{+}\right\}$

$(1)$ What is the complement of the language accepted by the $NFA?$ 

               $\overline{L}=\left\{\epsilon\right\}$
$(2)$ What is the language which accepts complement of $NFA?$ 

         

   

                 $L_{1}=\left\{\epsilon,(a+\epsilon)^{+}\right\}$ 

Please correct me if i'm wrong$?$   

---

No,  it is not correct as it is epsilon-nfa. In nfa,   we do not get a complement by complementing the state diagram. You have to complement the language.  So,  language accepted here is L={a+}.

So,  it's complement would be L'={€}

---

which one is not correct??

---

@Lakshman Patel RJIT

why the answer is not $a^{*}??$

If we draw complement diagram , isnot it coming $a^{*}??$

I mean according to this diagram ,what it means?

---

@srestha ma'am

It is $\epsilon$-NFA

And when we just toggled the state, we can't get the complement of $\epsilon$-NFA.

In my above comment $2^{nd}$ statement is not correct.

It is not a complement of above $\epsilon$-NFA. Because it also accepts $L=\{a^{+}\}.$

---------------------------------------------------------------------------------

$L=\{a,aa,aaa,...\}=\{a^{+}\}$

We can draw the DFA for this.

$L=\{a^{+}\}$

Now, we can complement the DFA

$L=\{\epsilon\}$

Reference:

• https://stackoverflow.com/questions/14802732/finding-the-complement-of-a-dfa
• https://www.cs.odu.edu/~toida/nerzic/390teched/regular/fa/complement.html
• https://web.stanford.edu/class/archive/cs/cs103/cs103.1142/lectures/13/Small13.pdf

---

@Lakshman Patel RJIT

yes, that I know, but what this diagram accepts??

is it $a^{*}$ or $\epsilon ??$

---

@srestha Ma'am

it will give $L=\{\epsilon,(a+\epsilon)^{+}\}=\{\epsilon,a^{+}\} = \{a^{\ast}\}$

and below automata is also giving the same output

---

So, ur answer is not matching, hence not correct. right??

We can conclude that , we cannot do complement of NFA. Complement only possible for DFA.

right??

---

Yes

---

Lakshman Patel RJIT

please check this - 

 1. Complement of language of a given NFA $\neq$  Language accepted by Complement of that given NFA.

2. Complement of language of a given DFA $=$  Language accepted by Complement of that given DFA.

 

---

I think you are right.

---

@MRINMOY_HALDER

 

 Complement of language of a given NFA ≠  Language accepted by Complement of that given NFA.

2. Complement of language of a given DFA =  Language accepted by Complement of that given DFA.

 

 

Can u explain these lines ?  Where u got these line?

---

"Complement of language of a given NFA ≠≠  Language accepted by Complement of that given NFA. "

I think it is may or may not be equal. Please verify.

---

Correct.

In the case of NFA, by complementing automata we will not get the complement of language. In some cases, it may give complement of the language but it’s not always true. That’s why there no concept of a complement of NFA.

---

L= { a, a.$\epsilon$.$\epsilon$.a, a.$\epsilon$.$\epsilon$.a.$\epsilon$.$\epsilon$.a, ……}={a,aa,aaa,….}

a.$\epsilon$=$\epsilon$.a=a. here $\epsilon$ is empty string(“”).

The complement of a NFA doesn't give us the complement of the language it is accepting. Better you find out the language it is accepting and then complement the language.

I think this is the most important part which is being ignored. 

---

What is the meaning of E(sigma)={a} and e(epsilon) is the empty string. e is epsilon I understand but what is the meaning of E={a} is empty???

---

Detailed Video Solution & Complete Analysis of NFA Complement: https://youtu.be/jpciKGP4gT4

---

IF WE MAKE FINAL STATE AS NONFINAL AND NONFINAL AS FINAL THEN ALSO ONLY EPISLON IS ACCEPTED 

---

@ankit2024 if you do that then a* will be answer and in nfa we can't make final to non final and non final to final for complemnt it can be only happen in dfa 

---

Ok got it

---

Wrong method for NFA

Answer 1

The language being accepted is $a^+$. So, complement of the language is $\{\epsilon\}$.

Comments

Don't Stuck at any where.... As a Gate aspirant you should read question carefully..

They are asking compliment of language , not asking about compliment of NFA Machine..

NFA accepts {a+}

Complement of the Language ={epsilon}

Complement of NFA MACHINE ={a*}

---

U r correct 💯

---

but the thing we exchange non finals with final for only complete dfa .

Answer 2

NFA accepts the language L=a+ and ∑={a}

the complement of L=∑*- a+=a*-a+={∊}

so answer is B

Comments

Complement does not work with NFA always. I don't think this approach is correct even though it works for this example.

---

@tusharp he did not make the complement of NFA, he made the complement of language which always works

Answer 3

Ans.

Answer 4

the language is a+ .....  compliment is {$\varepsilon$}

Comments

IF WE MAKE FINAL STATE AS NONFINAL AND NONFINAL AS FINAL THEN ALSO ONLY EPISLON IS ACCEPTED 

 

Answer 5

one more way is to convert this epsilon nfa to nfa and then take complement of the language but the only careful point is that the question has asked about the langauge formed by complement of the language accpeted by such nfa.

in nfa complementation doesnt work the same way that dfa does. so "complement of language accepted by nfa" and "complement of the machine" are two different things in case of nfa

Answer 6

option c is right