## 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.

### MSC:

 68Q45 Formal languages and automata

### Keywords:

free monoid; prefix code; syntactic properties of languages

Zbl 0563.00019