For a given language $L \subseteq \Sigma^*$, let

$\qquad \displaystyle S_L(z) = \sum\limits_{n \geq 0} |L \cap \Sigma^n|\cdot z^n$

the (ordinary) [generating function](https://en.wikipedia.org/wiki/Generating_function) of $L$, i.e. its sequence of word counts per length.

The following statement holds [[FlSe09](http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html), p52]:

$\qquad \displaystyle L \in \mathrm{REG} \quad \Longrightarrow \quad S_L \text{ rational}$

That is, $S_L(z) = \frac{P(z)}{Q(z)}$ with $P,Q$ polynomials.

So any language whose generating function is *not* rational is not regular. Unfortunately, all [linear languages](https://en.wikipedia.org/wiki/Linear_language) also have rational generating functions¹ so this method won't work for the simpler non-regular languages. Another drawback is that obtaining $S_L$ (and showing that it is not rational) can be hard.

**Example:** Consider the language of correctly nested parentheses words, i.e. the [Dyck language](https://en.wikipedia.org/wiki/Dyck_language). It is generated by the [unambiguous grammar](https://en.wikipedia.org/wiki/Ambiguous_grammar)

$\qquad \displaystyle S \to [S]S \mid \varepsilon$

which can be translated into the equation 

$\qquad \displaystyle S(z) = z^2S^2(z) + 1$

one solution (the one with all positive coefficients) of which is 

$\qquad \displaystyle \mathcal{S}(z) = \frac{1 - \sqrt{1 - 4z^2}}{2z^2}$. 

As $S_L = \mathcal{S}$ [[Kuic70](http://www.sciencedirect.com/science/article/pii/S0019995870901051)] and $\mathcal{S}$ is not rational, the Dyck language is not regular.

---
 1. The proof for the statement for regular languages works via grammars and transfers to linear grammars immediately (commutativity of multiplication).

---
$\ \ $ [FlSe09] [*Analytic Combinatorics*](http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html) by P. Flajolet and R. Sedgewick (2009)  
$\ \ $ [Kuic70] [*On the Entropy of Context-Free Languages*](http://www.sciencedirect.com/science/article/pii/S0019995870901051) by W. Kuich (1970)