Cone (formal languages) explained

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

l{S} of languages such that l{S} contains at least one non-empty language, and for any L \in l{S} over some alphabet \Sigma ,

• if

h is a homomorphism from \Sigma ^{\ast} to some \Delta ^{\ast} , the language h(L) is in l{S} ;

• if

h is a homomorphism from some \Delta ^{\ast} to \Sigma ^{\ast} , the language h ^{-1} (L) is in l{S} ;

• if

R is any regular language over \Sigma , then L\cap R is in l{S} .

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

T , mapping a language L over the input alphabet into another language T(L) 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

T can be decomposed into cone operations. In fact, there exists a normal form for this decomposition, which is commonly known as Nivat's Theorem:^[1] Namely, each such T can be effectively decomposed asT(L) = g(h ^{-1} (L) \cap R) , where g, h are homomorphisms, and R is a regular language depending only on T .

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

\{a,b\} that removes every second b 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

• Seymour . Ginsburg . Sheila . Greibach. Sheila Greibach . Abstract Families of Languages . Conference Record of 1967 Eighth Annual Symposium on Switching and Automata Theory, 18–20 October 1967, Austin, Texas, USA . 1967 . 128–139 . IEEE.
• Nivat . Maurice. Maurice Nivat. 10.5802/aif.287 . Transductions des langages de Chomsky . . 18. 1. 339–455. 1968 . free.
• Seymour Ginsburg, Algebraic and automata theoretic properties of formal languages, North-Holland, 1975, .
• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. . Chapter 11: Closure properties of families of languages.
• Book: Mateescu . Alexandru . Salomaa. Arto . Arto Salomaa. Grzegorz. Rozenberg. Arto. Salomaa . Handbook of Formal Languages. Volume I: Word, language, grammar . Springer-Verlag . 1997 . 175–252 . Chapter 4: Aspects of Classical Language Theory . 3-540-61486-9.

External links

• Encyclopedia of mathematics: Trio, Springer.

Notes and References

1. cf.