Cone (formal languages)
In the context of formal language theory, a cone refers to a family of formal languages closed under certain operations. These operations typically include nonerasing homomorphisms, inverse homomorphisms, and intersection with regular languages. The concept of a cone is crucial for classifying families of languages and understanding their relationships.
Formally, a family of languages L is a cone (sometimes called a Full Abstract Family of Languages or AFL) if it satisfies the following properties:
-
L is closed under nonerasing homomorphisms: If L is in L and h is a nonerasing homomorphism, then h(L) is in L. A nonerasing homomorphism is a function that maps symbols from one alphabet to strings of symbols from another alphabet, with the restriction that no symbol maps to the empty string.
-
L is closed under inverse homomorphisms: If L is in L and h is a homomorphism, then h-1(L) is in L. The inverse homomorphism maps a set of strings from one alphabet back to strings in another alphabet that are mapped to the original strings by h.
-
L is closed under intersection with regular languages: If L is in L and R is a regular language, then L ∩ R is in L.
The closure properties of cones are vital for establishing hierarchies within formal language theory. Demonstrating that a language family constitutes a cone provides insights into its generative power and the computational models needed to recognize languages within that family. The investigation of cones allows researchers to identify languages sharing similar properties and to compare the expressiveness of different formalisms.
A related concept is that of a full trio, which satisfies only conditions 1 and 2. Full trios are less restrictive than cones.