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.
Best answer 89 votes 89 votes The language being accepted is $a^+$. So, complement of the language is $\{\epsilon\}$. Arjun answered Aug 21, 2014 selected Aug 22, 2014 by gatecse Arjun comment Share Follow See all 16 Comments See all 16 16 Comments reply PEKKA commented Nov 18, 2016 reply Follow Share How will aa be produced here ? after one a it goes to final state . What hapens on reading the 2nd 'a' ? 3 votes 3 votes sudsho commented Dec 2, 2016 reply Follow Share @gokou from final state using epsilon we can again come back to start state..and the process repeats!! 22 votes 22 votes habedo007 commented Nov 27, 2017 reply Follow Share Is this true?: If L = $\phi$ then L* = $\{\epsilon\}$ 0 votes 0 votes Sahil1994 commented Jan 14, 2018 reply Follow Share @habed yes true 0 votes 0 votes Abhilash Mishra commented Apr 12, 2018 reply Follow Share Sir, I have the same query. If in complementation, arrows are not reversed, then there are always epsilon paths from the non-final state(middle state) to the final states. So language accepted should be a*. But again, your solution also seems very right. I fail to understand what's going on. It would be really helpful if you can clarify this doubt. 0 votes 0 votes Prashant. commented Apr 12, 2018 reply Follow Share In Complementation, arrows are not reversed but final states are exchanged so that change the whole language . Example: make DFA of a* now if you complete the DFA then there is no Final state i.e. accept Nothing. Take another language a*b* make DFA of it and complement it , Then you get the idea. 5 votes 5 votes mb14 commented Aug 8, 2018 reply Follow Share Plss someone clarify why answer is not a*. According to me suppose we give input string 'aaa'. Then using epsilon transitions we can reach the final state. overall it can generate a*. Plss help. 0 votes 0 votes talha hashim commented Sep 7, 2018 reply Follow Share @mbisht complement rule is not applicable on NFA it is applicable on dfa so first convert it into dfa then come to point .....u should read prashant sir comment 2 votes 2 votes mb14 commented Sep 8, 2018 reply Follow Share Thankss...I got it. 0 votes 0 votes tusharp commented Nov 17, 2018 reply Follow Share from final state using epsilon we can again come back to start state..and the process repeats!! using the same logic, even in complement of NFA this should work. Plz help 0 votes 0 votes vupadhayayx86 commented Dec 12, 2018 reply Follow Share @Arjun sir how dfa will look like for this nfa ? Can we just remove epsilon transitions and can consider it as dfa? Or shall we use nfa to dfa conversion method? 0 votes 0 votes Alakhator commented Jul 7, 2019 reply Follow Share When we complement a NFA does the language always get complemented ? plz explain @arjun sir 1 votes 1 votes shivam001 commented Jul 22, 2019 reply Follow Share sir complement of finite automata only work for DFA , not for NFA . can you plz explain ? 0 votes 0 votes KUSHAGRA गुप्ता commented Dec 2, 2019 reply Follow Share $1.\ \varepsilon- NFA\ to\ NFA$ $2.\ NFA\ to\ DFA$ $3.\ Compliment$ $Ans: \varepsilon$ 20 votes 20 votes Madhab commented Aug 31, 2020 reply Follow Share very good explanation . 0 votes 0 votes Subbu. commented Sep 10, 2021 i edited by JAINchiNMay Nov 16, 2022 reply Follow Share 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*} 13 votes 13 votes Please log in or register to add a comment.
42 votes 42 votes NFA accepts the language L=a+ and ∑={a} the complement of L=∑*- a+=a*-a+={∊} so answer is B vnc answered Nov 27, 2015 vnc comment Share Follow See all 2 Comments See all 2 2 Comments reply tusharp commented Nov 17, 2018 reply Follow Share Complement does not work with NFA always. I don't think this approach is correct even though it works for this example. 0 votes 0 votes Gurdeep Saini commented Jul 9, 2019 reply Follow Share @tusharp he did not make the complement of NFA, he made the complement of language which always works 3 votes 3 votes Please log in or register to add a comment.
13 votes 13 votes Ans. varunraj answered Mar 16, 2018 varunraj comment Share Follow See all 0 reply Please log in or register to add a comment.
4 votes 4 votes the language is a+ ..... compliment is {$\varepsilon$} Tarani Behera answered Nov 28, 2015 edited Jan 14, 2018 by Puja Mishra Tarani Behera comment Share Follow See all 0 reply Please log in or register to add a comment.