closure properties

Show Summary Details

Quick Reference

A class L of formal languages is closed under an operation f if the application of f to languages in L always yields a language in L. For example, if, for any L1 and L2 in L, L1L2 is also in L, then L is closed under union. Typical operations considered are: union, intersection, complement, intersection with regular set; concatenation, Kleene star; image under homomorphism, inverse homomorphism, substitution; gsm-mapping, etc.


Most familiar classes of languages are closed under these operations. The detailed picture for the Chomsky hierarchy is given in the table. Certain classes of languages, e.g. regular languages, can be uniquely characterized by their closure properties.

Closure properties. Closure properties for Chomsky hierarchy

Subjects: Computing.

Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.