Computer Science Asked on November 28, 2021
Let $Sigma$ be an alphabet and let $L$ be a language over it with the following properties:
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 }$.
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP