2 votes 2 votes Suppose we have a language $L$ and it is finite, now if we take a complement of language $L$ than what can we say about the language $L^{ / }$ ? a.) Language is decidable b.) Undecidable?? Theory of Computation theory-of-computation + – focus _GATE asked Nov 6, 2015 focus _GATE 948 views answer comment Share Follow See 1 comment See all 1 1 comment reply amarVashishth commented Nov 6, 2015 reply Follow Share do not provide bad headings to questions It should have been titled something like : "Decidability of Complement of a finite Language" 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes L = Regular L' = Regular (Since Complement of a Regular Language is Regular ) And Every Regular Language is Decidable. Aditya answered Nov 6, 2015 Aditya comment Share Follow See all 3 Comments See all 3 3 Comments reply focus _GATE commented Nov 7, 2015 reply Follow Share i was thinking that, if we do the complement of finite language than the complement of language may be finite or may be infinite..so we cannot decide either the complement will be finite or infinte therefore it is undecidable. correct me plzz.?? 0 votes 0 votes अनुराग पाण्डेय commented Nov 7, 2015 reply Follow Share I guess Decidability of a Language should mean something like "membership problem of that Language" that is "Give me any string w & I will tell you whether w is in the language or not" & since L is finite, it is regular for sure. Hence we can check whether w is in L or not, if it is not in L then it must be in L'. So it should be Decidable. 1 votes 1 votes Arjun commented Nov 7, 2015 reply Follow Share Complement of all finite languages are infinite- but that doesn't make them undecidable. Actually undecidable term is to be used for problems and not languages- in language terms it must be not recursive. 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes L is finite, so we can construct DFA for that . Now complement of that language is just do nonfinal state as final and also final state as nonfinal. So, it is also a DFA. So, it must be decidable srestha answered Nov 6, 2015 srestha comment Share Follow See all 0 reply Please log in or register to add a comment.