# Generating function of non-regular language

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?

• 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... – D.W. May 22 '17 at 16:08
• @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. – openspace May 22 '17 at 18:15

## 2 Answers

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.

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