Cone (formal languages)

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 [math]\displaystyle{ \mathcal{S} }[/math] of languages such that [math]\displaystyle{ \mathcal{S} }[/math] contains at least one non-empty language, and for any [math]\displaystyle{ L \in \mathcal{S} }[/math] over some alphabet [math]\displaystyle{ \Sigma }[/math],

• if [math]\displaystyle{ h }[/math] is a homomorphism from [math]\displaystyle{ \Sigma^\ast }[/math] to some [math]\displaystyle{ \Delta^\ast }[/math], the language [math]\displaystyle{ h(L) }[/math] is in [math]\displaystyle{ \mathcal{S} }[/math];
• if [math]\displaystyle{ h }[/math] is a homomorphism from some [math]\displaystyle{ \Delta^\ast }[/math] to [math]\displaystyle{ \Sigma^\ast }[/math], the language [math]\displaystyle{ h^{-1}(L) }[/math] is in [math]\displaystyle{ \mathcal{S} }[/math];
• if [math]\displaystyle{ R }[/math] is any regular language over [math]\displaystyle{ \Sigma }[/math], then [math]\displaystyle{ L\cap R }[/math] is in [math]\displaystyle{ \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]\displaystyle{ \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.

Relation to Transducers

A finite state transducer is a finite state automaton that has both input and output. It defines a transduction [math]\displaystyle{ T }[/math], mapping a language [math]\displaystyle{ L }[/math] over the input alphabet into another language [math]\displaystyle{ T(L) }[/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]\displaystyle{ T }[/math] can be decomposed into cone operations. In fact, there exists a normal form for this decomposition, which is commonly known as Nivat's Theorem: Namely, each such [math]\displaystyle{ T }[/math] can be effectively decomposed as [math]\displaystyle{ T(L) = g(h^{-1}(L) \cap R) }[/math], where [math]\displaystyle{ g, h }[/math] are homomorphisms, and [math]\displaystyle{ R }[/math] is a regular language depending only on [math]\displaystyle{ T }[/math].

Altogether, this means that a family of languages is a cone if and only if 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]\displaystyle{ \{a,b\} }[/math] that removes every second [math]\displaystyle{ 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.

See also

• Abstract family of languages

References

• Ginsburg, Seymour; Greibach, Sheila (1967). "Abstract Families of Languages". IEEE. pp. 128–139. 

• Nivat, Maurice (1968). "Transductions des langages de Chomsky". Annales de l'Institut Fourier 18 (1): 339–455. doi:10.5802/aif.287. 
• Seymour Ginsburg, Algebraic and automata theoretic properties of formal languages, North-Holland, 1975, ISBN:0-7204-2506-9.
• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN:0-201-02988-X. Chapter 11: Closure properties of families of languages.
• Mateescu, Alexandru; Salomaa, Arto (1997). "Chapter 4: Aspects of Classical Language Theory". in Rozenberg, Grzegorz; Salomaa, Arto. Handbook of Formal Languages. Volume I: Word, language, grammar. Springer-Verlag. pp. 175–252. ISBN 3-540-61486-9. 

External links

• Encyclopedia of mathematics: Trio, Springer.