A characterization of dense languages (Q799823)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A characterization of dense languages |
scientific article |
Statements
A characterization of dense languages (English)
0 references
1984
0 references
Let X be a finite alphabet with more than one letter. Let S be a language over X, i.e. a subset of the free monoid generated by X. Recall that a language is called disjunctive if its principal congruence \((=syntactic\) congruence) is the equality relation on \(X^*\). If S is a disjoint union of infinitely many disjunction languages, it is said to be disjunctive- splittable. On the other hand S is called dense if for every \(x\in X\), \(S\cap X^*xX^*\neq\emptyset \). The purpose of the note is to prove that S is dense iff it is disjunctive-splittable.
0 references
finite alphabet
0 references
principal congruence
0 references
syntactic congruence
0 references
disjunction languages
0 references
disjunctive-splittable
0 references