Samiksha Jaiswal (Editor)

Cone (formal languages)

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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.

Contents

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 S of languages such that S contains at least one non-empty language, and for any L ∈ S over some alphabet Σ ,

  • if h is a homomorphism from Σ ∗ to some Δ ∗ , the language h ( L ) is in S ;
  • if h is a homomorphism from some Δ ∗ to Σ ∗ , the language h − 1 ( L ) is in S ;
  • if R is any regular language over Σ , then L ∩ R is in 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: Namely, each such T can be effectively decomposed as T ( L ) = g ( h − 1 ( L ) ∩ 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

    Cone (formal languages) Wikipedia
    (Text) CC BY-SA


    Similar Topics