0
$\begingroup$

Let L={F| F is a finite language over Σ} which of the following operation is not closed for L?

a. intersection

b. union

c. complement

d. none of the above

I thought the ans as d as all finite languages are regular and since regular languages are closed under all hence d seemed apt to me. But ans given is C which is correct C or D? and Why?

| cite | improve this question | |
$\endgroup$
1
$\begingroup$

There are infinitely many strings over any alphabet, so if you pick any finite language, there are infinitely many strings not in it. In other words, there are infinitely many strings in the complement of any finite language.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But what about all finite languages are regular languages and RL are closed under complementation.. $\endgroup$ – Turing101 Aug 9 '19 at 4:27
  • 2
    $\begingroup$ The complement of a finite language is a regular language that isn't finite. To give an analogy, the partner of every person is a person. Every man is a person, but it's not true that the partner of every man is a man. That is, the set of people is closed under taking partners, but the set of men isn't, even though all men are people. $\endgroup$ – David Richerby Aug 9 '19 at 8:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.