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. The concept of a cone is a more abstract notion that subsumes all of these families.

PropertyValue
dbpprop:abstract
  • 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. 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 <math>\mathcal{S}</math> of languages such that, for any <math>L \in \mathcal{S}</math> over some alphabet <math>\Sigma</math>, if <math>h</math> is an homomorphism from <math>\Sigma^\ast</math> to some <math>\Delta^\ast</math>, the language <math>h(L)</math> is in <math>\mathcal{S}</math>; if <math>h</math> is an homomorphism from some <math>\Delta^\ast</math> to <math>\Sigma^\ast</math>, the language <math>h^{-1}(L)</math> is in <math>\mathcal{S}</math>; if <math>R</math> is any regular language over <math>\Sigma</math>, then <math>L\cap R</math> is in <math>\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>\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. 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.
dbpprop:hasPhotoCollection
dbpprop:reference
rdfs:comment
  • 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. The concept of a cone is a more abstract notion that subsumes all of these families.
rdfs:label
  • Cone (formal languages)
owl:sameAs
skos:subject
foaf:page
is dbpprop:disambiguates of