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 Tuhin Dutta commented Nov 22, 2017 reply Follow Share 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? 0 votes 0 votes akash.dinkar12 commented Jan 29, 2018 reply Follow Share arrows will not be reversed..... 4 votes 4 votes Lakshman Bhaiya commented Jan 14, 2019 i edited by Lakshman Bhaiya Sep 7, 2019 reply Follow Share Assume $\sum=\{a\}$ and $\epsilon$ is the empty string. $L=\left\{a^{+}\right\}$ $(1)$ What is the complement of the language accepted by the $NFA?$ $\overline{L}=\left\{\epsilon\right\}$ $(2)$ What is the language which accepts complement of $NFA?$ $L_{1}=\left\{\epsilon,(a+\epsilon)^{+}\right\}$ Please correct me if i'm wrong$?$ 2 votes 2 votes chandratushar19 commented Jan 17, 2019 reply Follow Share No, it is not correct as it is epsilon-nfa. In nfa, we do not get a complement by complementing the state diagram. You have to complement the language. So, language accepted here is L={a+}. So, it's complement would be L'={€} 18 votes 18 votes Lakshman Bhaiya commented Jan 17, 2019 reply Follow Share which one is not correct?? 0 votes 0 votes srestha commented Sep 7, 2019 reply Follow Share @Lakshman Patel RJIT why the answer is not $a^{*}??$ If we draw complement diagram , isnot it coming $a^{*}??$ I mean according to this diagram ,what it means? 2 votes 2 votes Lakshman Bhaiya commented Sep 7, 2019 i edited by Lakshman Bhaiya Sep 7, 2019 reply Follow Share @srestha ma'am It is $\epsilon$-NFA And when we just toggled the state, we can't get the complement of $\epsilon$-NFA. In my above comment $2^{nd}$ statement is not correct. It is not a complement of above $\epsilon$-NFA. Because it also accepts $L=\{a^{+}\}.$ --------------------------------------------------------------------------------- $L=\{a,aa,aaa,...\}=\{a^{+}\}$ We can draw the DFA for this. $L=\{a^{+}\}$ Now, we can complement the DFA $L=\{\epsilon\}$ Reference: https://stackoverflow.com/questions/14802732/finding-the-complement-of-a-dfa https://www.cs.odu.edu/~toida/nerzic/390teched/regular/fa/complement.html https://web.stanford.edu/class/archive/cs/cs103/cs103.1142/lectures/13/Small13.pdf 10 votes 10 votes srestha commented Sep 7, 2019 reply Follow Share @Lakshman Patel RJIT yes, that I know, but what this diagram accepts?? is it $a^{*}$ or $\epsilon ??$ 0 votes 0 votes Lakshman Bhaiya commented Sep 7, 2019 i edited by Lakshman Bhaiya Sep 7, 2019 reply Follow Share @srestha Ma'am it will give $L=\{\epsilon,(a+\epsilon)^{+}\}=\{\epsilon,a^{+}\} = \{a^{\ast}\}$ and below automata is also giving the same output 1 votes 1 votes srestha commented Sep 7, 2019 reply Follow Share So, ur answer is not matching, hence not correct. right?? We can conclude that , we cannot do complement of NFA. Complement only possible for DFA. right?? 1 votes 1 votes Lakshman Bhaiya commented Sep 7, 2019 reply Follow Share Yes 0 votes 0 votes mrinmoyh commented Sep 16, 2019 reply Follow Share Lakshman Patel RJIT please check this - 1. Complement of language of a given NFA $\neq$ Language accepted by Complement of that given NFA. 2. Complement of language of a given DFA $=$ Language accepted by Complement of that given DFA. 1 votes 1 votes Lakshman Bhaiya commented Sep 16, 2019 reply Follow Share I think you are right. 0 votes 0 votes srestha commented Sep 16, 2019 reply Follow Share @MRINMOY_HALDER Complement of language of a given NFA ≠ Language accepted by Complement of that given NFA. 2. Complement of language of a given DFA = Language accepted by Complement of that given DFA. Can u explain these lines ? Where u got these line? 1 votes 1 votes 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 Show 13 previous comments 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.