2k views

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

retagged | 2k 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?

The language being accepted is $a^+$. So, complement of the language is $\{\epsilon\}$.
answered by Veteran (332k points)
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+={∊}

so answer is B
answered by Boss (7k points)
the language is a+ .....  compliment is {$\varepsilon$}
answered by (99 points)
edited ago
–1 vote

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

answered by (27 points)
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
answered by Boss (7k points)

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