complement of the Finite Automata

Question

For below question assume you have input set = {a,b}

Q1. Complement of the NFA accepting language L is equivalent to complement of the that language L. {True/False}

Q2. What will be the complement of NFA accepting only epsilon?

Answer 1

1) the first statement is false..the complement of NFA need not be complement of language..means it may or may not .....but complement of DFA is always the COMPLEMENT of given language...

2) the answer is (a+b)^+.......here NFA gives complement of language...

YOU CAN SAY ....COMPLEMENT OF NFA IS NEVER ALWAYS COMPLEMENT OF LANGUAGE...IT MAY OR MAY NOT.....

answer of 2nd is as follows...

Comments

yes i got that ...i have constructed DFA.....else answer would we PHI....but more...accurately THE ANSWER DEPEND ON CONSTRUCTION OF NFA.....means not for this question ...but if question is different then we may get diff answers..for complement of language....

---

why you need a different question?

in this example too , we have two NFA , one that is DFA and other that we designed by ignoring dead states and both have different complement.

but what is NFA? it's machine whose state diagram you draw. so you talk about it by it's state diagram.so for a particular state diagram , we have unique complement.

Hello shubhanshu , i answered it phi  and now edit with phi again. it was an instantaneous mistake in b/w, which is now resolved.

---

Then think with NFA accepting strings starting with a

Answer 2

1) It's a false statement.

Let suppose we have one NFA for some regular language and it's M. so what does it mean by complement of this NFA it's basically M' now you're asking

whether for NFA L(M')=(L(M))'?

this statement is true for DFA , but not for NFA , reason is simple , for DFA , every final state is accepting state and every Non-final state is rejecting state , same is not true for NFA , because it may happen that for some i/p we 're reaching some final state and non-final state as well.

How does we define L(NFA)? it's like for some input string W , after complete scanning of W , if at least one final state is reached , then this W is part of language.Let suppose after consuming i/p W , we reach 3 states q1,q2,q3 so if out of those 3 states , if at least one is final state then it's acceptable input. But for DFA , it can't happen for a particular i/p only one final state is possible.

L(M') is achieved by just convert final state to non-final state and vice versa.

so you can see for i/p W , q1,q2 was non-final states and q3 was final state and it was acceptable i/p in original NFA but in complement of NFA , q1,q2 are final state and q3 is non-final state , but as w is still reaching atleast one final state , it's still valid i/p , does it happen in complement of language? No.

Complement of language is defined by (L(M))'= ∑*-L(M) , it's not that easy to evaluate but we just know that complement of a language is everything that is not part of language.

2)here we have only one final state , make this non-final state , what we got? Nothing but ∅.

Comments

i answered this issue in my last comment.

for a particular language, there can be infinity NFA possible,

so may be many complements , but we're talking about complement of NFA , which corresponds to particular state diagram.in general NFA is that is free from dead state , for which answer is phi.

---

so you want to say:

if NFA accepting null only then complement of NFA accepting phi.

---

@Anu007 in the question it is asked about NFA not Epsilon NFA.