1
$\begingroup$

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

  1. if $w\in L$ then there exists $v\in \Sigma^*$ such that $wv \in L$ and for every $s\in \Sigma$ the word $wvs$ does not lie in $L$
  2. $wv\in 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:= |\{w\in 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):= \limsup\limits_{n\to\infty} \frac{\log\gamma_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) = \{ w\in L \mid \forall s\in \Sigma \,ws \text{ is not in } L \}$.

$\endgroup$
  • 1
    $\begingroup$ Do you have a specific language in mind? $\endgroup$ – Yuval Filmus Jul 22 at 16:40
  • 2
    $\begingroup$ Assume that the language contains a word with more than $0$ letters: $\omega \in L, \omega = \alpha x , |\alpha |\geq 0, x\in\Sigma$. By property (3): $\alpha \in L$. But by property (1) $\alpha x \notin L$ for all $x\in \Sigma$. Hence we have a contradiction. Your languages only contain the empty word $\varepsilon$ or are completely empty. $\endgroup$ – plshelp Jul 22 at 17:18
  • 1
    $\begingroup$ No, you're mistaken. You represent $w = \alpha x$, where $x\in \Sigma$. The (1) states only that there's a continuation for $\alpha$ that cannot be continued to a word in $L$ that itself cannot be continued. $\endgroup$ – John Jul 22 at 19:34
  • 1
    $\begingroup$ There are multiple such languages. You need to be more specific. $\endgroup$ – Dmitry Jul 23 at 21:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.