Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9655864 | Electronic Notes in Theoretical Computer Science | 2005 | 13 Pages |
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
Jakub Kozik,