In automata theory we study formal languages like Regular, CF, CS and etc. and each of them have their own closure properties under union, intersection, star and etc. . I like to know, why it is important to study such properties?

  • 1
    $\begingroup$ For the same reason that closure under any operation is a requirement in an algebra? $\endgroup$ – Benjamin R Apr 13 '16 at 7:46
  • $\begingroup$ This is between a list and an opinion-based question. I expect answers of two kinds: because 1) they are useful and 2) because they give structure to things, which is interesting (read: satisfies the inner nerd in researchers). $\endgroup$ – Raphael Apr 13 '16 at 8:03
  • $\begingroup$ I disagree with @Raphael. The answer to this question will be very useful for students understanding the purpose of various parts of formal languages. It's not opinion based like asking what the favourite formal language operator. $\endgroup$ – Dave Clarke Apr 13 '16 at 8:46
  • $\begingroup$ @DaveClarke That is true if you accept certain criteria of importance as objective truth. In my experience, non-TCSists often heavily disagree with this notion. Everyone from TCSist to programmer has an opinion on questions phrased like the one above, and we tend to get lots of bad answers as a result. If we want to avoid this here, I suggest we edit the question to fix a notion of importance, e.g. "important for TCS", "important for formal language theory", or "important in the educating of CSists". $\endgroup$ – Raphael Apr 13 '16 at 12:06

I think that the more fundamental question here is why study specific kinds of formal languages at all. One answer is that formal languages of specific kinds have been found useful in the construction of compilers. Another answer is that in the past they played an important part in artificial intelligence (nowadays statistical methods are more important).

Once we agree that regular languages and context-free languages are an interesting object of study, closure properties are basic mathematical properties of these objects. In fact, part of the beauty and appeal of the subject of regular languages is the large number of properties that they satisfy, including closure properties. Regular languages serve as a model for other families of languages, and one tries to mimic one's knowledge of regular languages on other families of languages.

Closure properties are also interesting beyond formal languages — Tychonoff's theorem in topology is one example.

Specific closure properties of regular languages have given rise to a new type of algebraic structure, Kleene algebras, which abstract some of the closure properties of regular languages and of context-free languages.

  • 1
    $\begingroup$ Not to mention AFLs, in particular cones! $\endgroup$ – Raphael Apr 13 '16 at 12:03

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.