TransWikia.com

Number of words of length n for special language

Computer Science Asked on November 28, 2021

Let $Sigma$ be an alphabet and let $L$ be a language over it with the following properties:

  1. if $win L$ then there exists $vin Sigma^*$ such that $wv in L$ and for every $sin Sigma$ the word $wvs$ does not lie in $L$
  2. $wvin L$ then $vw in L$
  3. It is prefix-closed, i.e. prefix of any word is still in the language.

Note that by the definition, it is not cyclic language. I’m trying to compute its growth function, by that I mean $gamma_n:= |{win L mid |w| = n}|$. I know about my specific case that it is not regular and my hypothesis is that function $Gamma(x) = sum_{n=1}^infty gamma_nx^n$ is not rational. However, I couldn’t find any information about these functions for non-regular languages. Maybe, there’s a formula that connects entropy of language, i.e. $e(L):= limsuplimits_{ntoinfty} frac{loggamma_n}{n}$ and the $Gamma$ function. Or for such a language there’s a way to describe its growth throughout the growth of the language $operatorname{End}(L) = { win L mid forall sin Sigma ,ws text{ is not in } L }$.

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP