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

Do Long Van

Acta Cybern. 7, 247-257 (1986).

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

Keywords:

infinitary code; infinitary languages; quasi-free monoid