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 $\mathcal$ of languages such that $\mathcal$ contains at least one non-empty language, and for any $L \in \mathcal$ over some alphabet $\Sigma$,
* if $h$ is a homomorphism from $\Sigma^\ast$ to some $\Delta^\ast$, the language $h(L)$ is in $\mathcal$;
* if $h$ is a homomorphism from some $\Delta^\ast$ to $\Sigma^\ast$, the language $h^(L)$ is in $\mathcal$;
* if $R$ is any regular language over $\Sigma$, then $L\cap R$ is in $\mathcal$.

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.

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'':cf.
Namely, each such $T$ can be effectively decomposed as
$T(L) = g(h^(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 $\$ 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

Notes

References

*

*
*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.
* {{cite book , last1=Mateescu , first1=Alexandru , last2=Salomaa, first2=Arto , editor1-first=Grzegorz, editor1-last=Rozenberg, editor2-first=Arto, editor2-last=Salomaa , title=Handbook of Formal Languages. Volume I: Word, language, grammar , publisher=Springer-Verlag , year=1997 , pages=175–252 , chapter=Chapter 4: Aspects of Classical Language Theory , isbn=3-540-61486-9

External links

Encyclopedia of mathematics: Trio
Springer.

Formal languages