𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the entropy of regular languages

✍ Scribed by Tullio Ceccherini-Silberstein; Antonio Machı̀; Fabio Scarabotti

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
422 KB
Volume
307
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

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 ÿnitely generated free groups and an additional application is presented.

📜 SIMILAR VOLUMES

Regular component decomposition of regul
Regular component decomposition of regular languages
✍ Y.J. Liu 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 198 KB

A language is regular if it can be recognized by a ÿnite automaton. According to the pumping lemma, every inÿnite regular language contains a regular subset of the form uv + w, where u; v; w are words and v is not empty. It is known that every regular language can be expressed as ( i∈I uiv + i wi) ∪

Squares of regular languages
Squares of regular languages
✍ Gerhard Lischke 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

The square of a language L is the set of all words pp where p ∈ L. The square of a regular language may be regular too or context-free or none of both. We give characterizations for each of these cases and show that it is decidable whether a regular language has one of these properties.

A note on ω-regular languages
A note on ω-regular languages
✍ Masako Takahashi; Hideki Yamasaki 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 647 KB
The single loop representations of regul
The single loop representations of regular languages
✍ H.J. Shyr; S.S. Yu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 782 KB

A regular language of the form UP' M' is called a single loop from the viewpoint of automata theory. It is known that every regular language can be expressed as (U,,,, U,L.;IV, )U F. where .4 is an index set, u,, ~1~ EX\*, c, EX~, i E A, and F is a finite set of words. This expression is called an s