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.
0 votes 0 votes The Σ= {a} and the given NFA accepts the strings {a, aa, aaa, aaaa, ……….} i.e. the language accepted by the NFA can be represented by the regular expression: {a+} Hence the complement of language is: {a* − a+} = {ϵ} varunrajarathnam answered Aug 16, 2020 varunrajarathnam comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Sometimes drawing a DFA is quite easier As we can clearly see, what is asked in the question shashankrustagi answered Dec 2, 2020 shashankrustagi comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes The given DFA is ϵ-NFA and has to be converted to DFA first. Because NFA and ϵ-NFA don’t have complements. After conversion to DFA, for complement, make final to non final state and non final to final state. Hence the language accepted is {ϵ}. Option B is correct rish1602 answered Jun 21, 2021 rish1602 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Ans option B deeptadas answered Jul 28, 2023 deeptadas comment Share Follow See all 0 reply Please log in or register to add a comment.