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

@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