2.4k views

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

1. $\phi$
2. $\{\epsilon\}$
3. $a^*$
4. $\{a , \epsilon\}$

edited | 2.4k views
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.....

The language being accepted is $a^+$. So, complement of the language is $\{\epsilon\}$.
selected by
How will aa be produced here ?  after one a it goes to final state . What hapens on reading the 2nd 'a'  ?
@gokou from final state using epsilon we can again come back to start state..and the process repeats!!
Is this true?: If L = $\phi$ then L* = $\{\epsilon\}$
@habed yes true
NFA accepts the language L=a+ and ∑={a}

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

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

Ans.

answered ago by Active (1.3k points)

answer is c.  for complement of the language: changes to be done in DFA is to make final states to non final states and make non final to final states. then check. so ais the answer

edited

@Monika its complement of the language i.e.Lc =∑*-L.

and you are talking about complement of machine .

@Monika the machine given is NFA and not DFA. So, you can't complement the machine and get the language. Correct answer is B
@Nipun No.Here qus is complement of the language accepted by the NFA not complement of machine accepted by NFA.
No. What he meant was - in order to change final states to non final state. You need to convert that NFA to DFA. Only then, the machine would accept the complement of the language.

No Actually i mean you can complement NFA but  in case of NFA , the language may or may not  complemented.

You can check this :https://gateoverflow.in/53393/theory-of-computation

option B

what steps do we have to follow while converting M to M bar.

1
2