abstract family of languages

views updated

abstract family of languages (AFL) There are many useful types of formal language, and classes often have similar properties. An AFL is a class of formal languages that is closed under all the following operations: union, concatenation, Kleene-plus (see Kleene star), intersection with regular set, Λ-free homomorphic image, and inverse homomorphic image (see homomorphism). An AFL is full if it is also closed under Kleene star and homomorphic image. The motivation for the concept of an AFL is to investigate properties of classes of languages that follow merely from the assumption of these closure properties. Each member of the Chomsky hierarchy is an AFL; all except for the class of context-free languages are full.