Cone (formal languages)

In formal language theory, a cone is an abstract family of languages of that is closed under homomorphism, inverse homomorphism, and intersection with a regular languages ^[1] More precisely, a cone is a non-empty family <math>\mathcal{S}</math> of languages such that, for any <math>L \in \mathcal{S}</math> over some alphabet <math>\Sigma</math>,

• if <math>h</math> is an homomorphism from <math>\Sigma^\ast</math> to some <math>\Delta^\ast</math>, the language <math>h(L)</math> is in <math>\mathcal{S}</math>;
• if <math>h</math> is an homomorphism from some <math>\Delta^\ast</math> to <math>\Sigma^\ast</math>, the language <math>h^{-1}(L)</math> is in <math>\mathcal{S}</math>;
• if <math>R</math> is any regular language over <math>\Sigma</math>, then <math>L\cap R</math> is in <math>\mathcal{S}</math>.

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 <math>\lambda</math> 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. 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.

Relation to Transducers

A finite state transducer is a finite state automaton that has both input and output. It defines a transduction <math>T</math>, mapping a language <math>K</math> over the input alphabet into another language <math>T(K)</math> over the output alphabet. Each of the cone operations (homomorphism, inverse homomorphism, intersection with a regular language) 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 <math>T</math> can be decomposed into cone operations. In fact, there exists a normal form for this decomposition <math>T(K) = g(h^{-1}(K \cap R))</math>, where <math>g, h</math> are homomorphisms, and <math>R</math> is a regular language determined by <math>T</math>. All together this means that a family of languages is a cone iff it is closed under finite state transductions. This is a very powerful set of operations. For instance one easily writes a (nondeterministic) finite state transducer with alphabet <math>\{a,b\}</math> that removes every second <math>b</math> in words of even length (and does not change words otherwise). Since the context-free languages form a cone, they are closed under this exotic operation.

References