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.6k views answer comment Share Follow See all 18 Comments See all 18 18 Comments reply Show 15 previous comments 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 moh_haris commented May 2 i edited by moh_haris May 2 reply Follow Share What is the meaning of E(sigma)={a} and e(epsilon) is the empty string. e is epsilon I understand but what is the meaning of E={a} is empty??? 0 votes 0 votes Please log in or register to add a comment.
–2 votes –2 votes 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 a* is the answer Monika Sharma answered Jun 11, 2016 • edited Jun 11, 2016 by Monika Sharma Monika Sharma comment Share Follow See all 6 Comments See all 6 6 Comments reply ManojK commented Jun 11, 2016 reply Follow Share @Monika its complement of the language i.e.Lc =∑*-L. and you are talking about complement of machine . 4 votes 4 votes nipun bansal commented Jul 6, 2016 reply Follow Share @Monika the machine given is NFA and not DFA. So, you can't complement the machine and get the language. Correct answer is B 4 votes 4 votes ManojK commented Jul 6, 2016 reply Follow Share @Nipun No.Here qus is complement of the language accepted by the NFA not complement of machine accepted by NFA. 0 votes 0 votes Arjun kp commented Jan 1, 2017 reply Follow Share 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. 0 votes 0 votes ManojK commented Jan 1, 2017 reply Follow Share 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 1 votes 1 votes Ram Swaroop commented Dec 26, 2018 reply Follow Share Complementation of language and complementation of nfa not same 0 votes 0 votes Please log in or register to add a comment.
–4 votes –4 votes option B Shubham Pandey 2 answered Sep 8, 2016 Shubham Pandey 2 comment Share Follow See 1 comment See all 1 1 comment reply rajatmyname commented Jun 12, 2017 reply Follow Share what steps do we have to follow while converting M to M bar. 0 votes 0 votes Please log in or register to add a comment.