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 recursive languages.^[1] The concept of a cone is a more abstract notion that subsumes all of these families.

More precisely, a cone is a non-empty family $\mathcal{S}$ of languages such that, for any $L \in \mathcal{S}$ over some alphabet $\Sigma$ ,

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

1 Relation to Transducers
2 See also
3 Notes
4 References
5 External links

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:^[2] Namely, each such T can be effectively decomposed as $T(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 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.

References

Ginsburg, Seymour; Greibach, Sheila (1967). "Abstract Families of Languages". Conference Record of 1967 Eighth Annual Symposium on Switching and Automata Theory, 18-20 October 1967, Austin, Texas, USA. IEEE. pp. 128-139.

Seymour Ginsburg, Algebraic and automata theoretic properties of formal languages, North-Holland, 1975, ISBN 0-7204-2506-9.

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 3540614869.

John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-029880-X. Chapter 11: Closure properties of families of languages.

External links

Encyclopedia of mathematics: Trio, Springer.

Cone (formal languages)

Contents

Relation to Transducers

See also

Notes

References

External links