×

Langages écrits par un code infinitaire. Théorème du défaut. (French) Zbl 0611.68046

If C is a class of (infinitary) codes, a language X is said to be written by a C-code if there is a \(Y\in C\) such that \(X\subseteq Y^*\). The author characterizes infinitary languages written by arbitrary codes, normal codes, prefix codes, and suffix codes. The basis of the quasi-free monoid generated by an infinitary language X written by a code has less elements than X has if X itself is not a code (”Theorem of defect”). A recognizable infinitary language written by a code can also be written by a recognizable code.
Reviewer: M.Armbrust

MSC:

68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
94A45 Prefix, length-variable, comma-free codes
PDF BibTeX XML Cite