toc

Question

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??

Comments

do not provide bad headings to questions

It should have been titled something like : "Decidability of Complement of a finite Language"

Answer 1

L = Regular

L' = Regular (Since Complement of a Regular Language is Regular )

And Every Regular Language is Decidable.

Comments

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.??

---

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.

---

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.

Answer 2

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