Closure Properties Definition/Meaning:
A class of formal
languages L is closed under an operation
ƒ
if the application of ƒ to
languages in L always yields a language in L. For example, if, for
any L1 and L2 in L,
L1, È L2
is also in L, then L is closed under union. Typical operations
considered are:
union, intersect ion,
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, are definable by their
closure properties.
|
