Article ID Journal Published Year Pages File Type
9655864 Electronic Notes in Theoretical Computer Science 2005 13 Pages PDF
Abstract
We define a density of a given language S in a given language L as an asymptotic probability that a randomly and uniformly chosen word of length n from L belongs to S. There are languages for which densities do not exist. We show that a problem of checking whether one regular language has a density in another regular language is decidable.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,