×

\(\mathcal{PS}\)-regular languages. (English) Zbl 1243.68217

The characterizations of regular languages by means of principal congruences, found already in the 1950s by J. Myhill and A. Nerode, provide natural starting points for algebraic approaches to the subject. These congruences are defined in terms of appropriate “contexts”. For example, two words \(x,y\in X^*\) are Nerode congruent with respect to a language \(L\) over an alphabet \(X\) exactly in the case when, for all words \(z\in X^*\) (here viewed as right contexts), \(xz\in L\) if and only if \(yz\in L\). H. Prodinger [Inf. Control 44, 36–46 (1980; Zbl 0431.68072)] observed that interesting classes of generalized regular languages can be obtained by demanding just that the set of right contexts on which the words \(x\) and \(y\) agree belongs to some given family of sets of a certain kind. In this paper, in each case a fixed set of two-sided contexts is considered.
A relation \(\Delta\subseteq X^*\times X^*\) is called a prefix-suffix set if it contains no two pairs \((s, t)\) and \((s', t')\) such that \(s\) is a proper prefix of \(s'\) or \(t\) is a proper suffix of \(t'\). For any language \(L\subseteq X^*\), the relation \(\approx_{\Delta,L}\) is defined by the condition that \(x\approx_{\Delta,L} y\) if for all \((s, t)\in\Delta\) and all \(u,v\in X^*\), \(suxvt\in L\Longleftrightarrow suyvt\in L\). This is a natural generalization of the usual syntactic (or Myhill) congruence, and \(L\) is said to be \(\Delta\)-regular if \(\approx_{\Delta,L}\) has a finite number of congruence classes. A language is \({\mathcal P}{\mathcal S}\)-regular if it is \(\Delta\)-regular for some prefix-suffix set \(\Delta\). The \({\mathcal P}\)- and \({\mathcal S}\)-regular sets are defined similarly by means of restricted sets of left and right contexts, respectively.
The paper contains many results concerning these notions. For example, \(\Delta\)-regular languages are characterized in terms of quotient languages, necessary and sufficient conditions under which all \(\Delta\)-regular languages are regular are given, and various closure properties are presented. The family of \({\mathcal P}{\mathcal S}\)-regular languages is also compared with the families of \({\mathcal P}\)-regular, \({\mathcal S}\)-regular, context-free and context-sensitive languages.

MSC:

68Q70 Algebraic theory of languages and automata
68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.

Citations:

Zbl 0431.68072
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Guo Y. Q., Acta Math. Sinica (Chinese) 26 pp 332– (1983)
[2] Lallement G., Semigroups and Combinatorial Applications (1979)
[3] DOI: 10.1016/S0019-9958(80)90123-0 · Zbl 0431.68072 · doi:10.1016/S0019-9958(80)90123-0
[4] Shyr H. J., Free Monoids and Languages (2001) · Zbl 0746.20050
[5] Zhang S. H., Acta Math. Sinica (Chinese) 31 pp 125– (1988)
[6] Zhang S. H., Acta Math. Sinica (Chinese) 30 pp 168– (1987)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.