𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the number of occurrences of a symbol in words of regular languages

✍ Scribed by Alberto Bertoni; Christian Choffrut; Massimiliano Goldwurm; Violetta Lonati

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

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the entropy of regular languages
On the entropy of regular languages
✍ Tullio Ceccherini-Silberstein; Antonio MachΔ±Μ€; Fabio Scarabotti πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 422 KB

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.

On lengths of words in context-free lang
On lengths of words in context-free languages
✍ Lucian Ilie πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 292 KB

We consider slender languages, that is, languages for which the number of words of the same length is bounded from above by a constant. It is known that the slender context-free languages are precisely the unions of paired loops, that is, ΓΏnite unions of sets of the form {uv n wx n y | nΒΏ0}. Analysi

Decidability of the consistency problem
Decidability of the consistency problem for regular symbolic picture description languages
✍ G. Costagliola; V. Deufemia; F. Ferrucci; C. Gravino πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 86 KB

In the paper we address the consistency problem for drawn symbolic picture grammars. In particular we prove that it is always possible to decide whether or not a regular grammar generates only consistent descriptions of drawn symbolic pictures.

On the number of words in the language {
On the number of words in the language {w Ξ΅ Οƒβˆ— ∣ w = wR}2
✍ R. Kemp πŸ“‚ Article πŸ“… 1982 πŸ› Elsevier Science 🌐 English βš– 659 KB

Let S be the set of all palindromes over B \*. It is well known. that the language S\* is an ultralinear, inherently ambiguous context-free language. In this paper we derive an explicit expression for the number of words of length n in S2. Furthermore, we show, that for card(P)> 1 the asymptotical d