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

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

Answer 1

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

Comments

$1.\ \varepsilon- NFA\ to\ NFA$

$2.\ NFA\ to\ DFA$

$3.\ Compliment$

$Ans: \varepsilon$

---

very good explanation .

---

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*}

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$}