In formal language theory, a cone is a set of formal languages that has some desirable closure properties enjoyed by some well-known sets of languages, in particular by the families of regular languages, context-free languages and the recursively enumerable languages. The concept of a cone is a more abstract notion that subsumes all of these families. A similar notion is the faithful cone, having somewhat relaxed conditions. For example, the context-sensitive languages do not form a cone, but still have the required properties to form a faithful cone. The terminology cone has a French origin. In the American oriented literature one usually speaks of a full trio. The trio corresponds to the faithful cone.
Definition
A cone is a family of languages such that contains at least one non-empty language, and for any over some alphabet,
The family of all regular languages is contained in any cone. If one restricts the definition to homomorphisms that do not introduce the empty word then one speaks of a faithful cone; the inverse homomorphisms are not restricted. Within the Chomsky hierarchy, the regular languages, the context-free languages, and the recursively enumerable languages are all cones, whereas the context-sensitive languages and the recursive languages are only faithful cones.
Relation to Transducers
A finite state transducer is a finite state automaton that has both input and output. It defines a transduction, mapping a language over the input alphabet into another language over the output alphabet. Each of the cone operations can be implemented using a finite state transducer. And, since finite state transducers are closed under composition, every sequence of cone operations can be performed by a finite state transducer. Conversely, every finite state transduction can be decomposed into cone operations. In fact, there existsa normal form for this decomposition, which is commonly known as Nivat's Theorem: Namely, each such can be effectively decomposed as , where are homomorphisms, and is a regular language depending only on. Altogether, this means that a family of languages is a cone if it is closed under finite state transductions. This is a very powerful set of operations. For instance one easily writes a finite state transducer with alphabet that removes every second in words of even length. Since the context-free languages form a cone, they are closed under this exotic operation.
