Languages and subshifts. (English) Zbl 0571.68059

Automata on infinite words, Ec. Printemps Inf. Théor., Le Mont Dore 1984, Lect. Notes Comput. Sci. 192, 138-146 (1985).
[For the entire collection see Zbl 0563.00019.]
Let A be a finite alphabet, \(A^*\) the free monoid over A. To every language \(L\subset A^*\), one can associate in a canonical way a subshift \(S_ L\subset A^{{\mathbb{Z}}}\). For instance the subshifts associated to rational languages are the so-called ”sofic” subshifts. More generally if \(L=X^*\) where X is a prefix code, then \(S_ L\) is called a ”coded” subshift. In this paper we present essential properties of sofic and coded subshifts. A special emphasis is put on the use of the syntactic properties of languages to deduce ”ergodic” properties of the associated subshifts.


68Q45 Formal languages and automata


Zbl 0563.00019