71 votes 71 votes What is the complement of the language accepted by the NFA shown below? Assume $\Sigma = \{a\}$ and $\epsilon$ is the empty string. $\phi$ $\{\epsilon\}$ $a^*$ $\{a , \epsilon\}$ Theory of Computation gatecse-2012 finite-automata easy theory-of-computation + – gatecse asked Aug 5, 2014 edited Feb 17, 2018 by kenzou gatecse 19.0k views answer comment Share Follow See all 17 Comments See all 17 17 Comments reply Show 14 previous comments King_in_the_north commented Nov 12, 2019 reply Follow Share "Complement of language of a given NFA ≠≠ Language accepted by Complement of that given NFA. " I think it is may or may not be equal. Please verify. 2 votes 2 votes raja11sep commented Jul 12, 2021 reply Follow Share 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. 1 votes 1 votes raja11sep commented Jul 12, 2021 reply Follow Share 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. 5 votes 5 votes Please log in or register to add a comment.
2 votes 2 votes 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 adarsh_1997 answered Jul 2, 2019 adarsh_1997 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes option c is right abhishekmehta4u answered Mar 28, 2019 edited Mar 28, 2019 by abhishekmehta4u abhishekmehta4u comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes L(M)=a+ L'(M)=sigma*-L(M) = {€} option b is answer manikantsharma answered Jul 5, 2019 manikantsharma comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Language being accepted by this NFA is : a+ complement of language = (∑*- a+)= (a* - a+) a*={ϵ,a,aa,aaa,....} a+={a,aa,aaa,......} so, complement of language = {ϵ} shivam001 answered Jul 22, 2019 reshown Jul 23, 2019 by shivam001 shivam001 comment Share Follow See all 0 reply Please log in or register to add a comment.