Context-free text grammars (Q1323383)

A text is a triple \(\tau=(\lambda,\rho_ 1,\rho_ 2)\) such that \(\lambda\) is a labeling function, and \(\rho_ 1\) and \(\rho_ 2\) are linear orders on the domain of \(\lambda\); hence \(\tau\) may be seen as a word \((\lambda,\rho_ 1)\) together with an additional linear order \(\rho_ 2\) on the domain of \(\lambda\). The order \(\rho_ 2\) is used to give to the word \((\lambda,\rho_ 1)\) its individual hierarchical representation (syntactic structure) which may be a tree but it may be also more general than a tree. In this paper we introduce context-free grammars for texts and investigate their basic properties. Since each text has its own individual structure, the role of such a grammar should be that of a definition of a pattern common to all individual texts. This leads to the notion of a shapley context-free text grammar also investigated in this paper.