On the entropy of regular languages
Let L be an irreducible regular language. Let W be a non-empty set of words (or sub-words) of L and denote by L-W = {v is an element of L:w not subset of v, For Allw is an element of W} the language obtained from L by forbidding all the words w in W. Then the entropy decreases strictly: ent(L-W) < ent(L). In this note we present a new proof of this fact, based on a method of Gromov, which avoids the Perron-Frobenius theory. This result applies to the regular languages of finitely generated free groups and an additional application is presented. (C) 2003 Elsevier B.V. All rights reserved.
entropy regular language free group oriented graph hopfianity