Let's say $\sum_{n \ge 1} a_{n}x^n$ is generating function for regular language $L$. $a_{n}$ is number of words with length $n$.

Find an example of generating function which isn't correspond for any regular language.

My attempt : I use the fact for any regular language there is exists $n_{0}$ $\lambda_{i}$ and $p_{i}$ : $a_{n} = \sum_{i} \lambda_{i}^{n} p_{i}$ and as example get language with $a_{n} = C_{n}$ , where $C_{n}$ is Catalan number. My teacher said that's not obvious and told me to get easier example. But I don't know useful criteria to find an example with contradiction about regularity. Any ideas?

  • 1
    $\begingroup$ Can you characterize which functions can arise as the generating function of a regular language? Do you know any theorems about that? If not, do you know any theorems about that for regular languages over a unary alphabet? If you search about unary languages on this site I bet you can figure out such a characterization, and I bet that would help you make progress towards your goal... $\endgroup$ – D.W. May 22 '17 at 16:08
  • $\begingroup$ @D.W. we consider only functions of form $\sum_{n \ge 0} a_{i}x^{n} = \frac{p(x)}{q(x)}$, where $a_{i} \in \mathbb{N}$. I know that $L$ is regular if and only if there is a finite automata correspond to this language. $\endgroup$ – openspace May 22 '17 at 18:15

If we apply a substitution that maps all letters of the alphabet to the same letter, we obtain a unary language. This shows that if $L$ is regular, then the set $\{n : L \cap \Sigma^n \neq \emptyset\}$ is eventually periodic. This shows that $\sum_{n=0}^\infty x^{n^2}$ corresponds to no regular language, for example.

  • $\begingroup$ So all we need to show that $L = \{a, aaaa, aaaaaaaaa \dots \}$ isn't regular? $\endgroup$ – openspace May 22 '17 at 19:57
  • $\begingroup$ That will suffice. $\endgroup$ – Yuval Filmus May 22 '17 at 20:24
  • $\begingroup$ then I misunderstood why this function correspond to non-regular language? $\endgroup$ – openspace May 22 '17 at 20:25
  • $\begingroup$ You can show that this language is non-regular in many ways. I'm sure you can find one. $\endgroup$ – Yuval Filmus May 22 '17 at 20:25

Here is a convoluted way:

  • There are inherently ambiguous CFLs (context-free languages), see e.g. (1).
  • Every regular language corresponds to a DFA.
  • Every DFA can be expressed by an unambiguous CFG.
  • Hence the inherently ambiguous CFLs cannot be regular.
  • Now the generating function for the inherently ambiguous CFLs do what you are looking for.

In particular (1) states: "if the counting generating function is transcendental over $\mathbb{Q}$, then the language is ambiguous", hence not regular.

  1. F. Bassino, C. Nicaud: Philippe Flajolet & Analytic Combinatorics: Inherent Ambiguity of Context-Free Languages.
  • $\begingroup$ So we should find $\frac{p(x)}{q(x)}$ with roots not in $\mathbb{Q}$ and in $\sum_{n \ge 0} a_{n} x^{n}$ all coefficients should be non-negative? $\endgroup$ – openspace May 22 '17 at 20:28

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.