closure properties

views updated

closure properties 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.