<p>There is a proof in the book of Kuich &amp; Salomaa, <em>Semirings, Automata, Languages</em> and another one in the paper of Panholzer, "Gröbner Bases and the Defining Polynomial of a Context-free Grammar Generating Function", J. of Automata, Languages and Combinatorics <strong>10</strong> (2005), 79–97.   I wish there were a simple and clear proof of the result.</p>

CC BY-SA 4.0
2020-07-26T15:42:28.030Z
But it's called _Chomsky-Schützenberger_ enumeration theorem; shouldn't there be a proof in their _Algebraic theory of context-free languages_ (Studies in Logic and the Foundations of Mathematic), which seems very accessible? However, I quickly looked through it but I couldn't find an explicit statement there (let alone a proof). If it isn't there, then the question rises where the name comes from...
Jori
CC BY-SA 4.0
2020-07-27T16:04:22.780Z
It is named for them because they had the basic statement and idea in their paper, although they did not supply a complete formal proof.    That is not unusual in mathematics.
Jeffrey Shallit
CC BY-SA 4.0
2020-07-27T17:28:29.017Z
Oh I see, no that isn't at all uncommon. But how big is the gap between the ideas that Chomky and Schützenberger provide and the actual proof? Because from casual glancing both Kuich&Salomaa and Panholzer need quite a bit of machinery to get there (I don't know how much because there is no explicitly delineated proof in those either, as far as I can tell). How much of the Kuich-Salomaa book do you need?
Jori
CC BY-SA 4.0
2020-07-28T18:48:51.190Z
The ingredient that is needed is some guarantee that when you take an unambiguous CFG and convert it to a system of algebraic equations in the almost-trivial way described by Chomsky and Schützenberger, that there indeed exists a solution to this system in power series, and that it is unique.
Jeffrey Shallit
CC BY-SA 4.0
2020-07-28T19:39:00.940Z
So what would I need to read in the Kuich-Salomaa book? I'm a logician, so this is not really my topic, but I've always wanted to learn about this proof; I remember reading that the transcendence of $\pi$ was equivalent to some language being inherently ambiguous and found that quite neat, although I'm not sure I remember the details correctly.
Jori
CC BY-SA 4.0
2020-07-29T06:23:03.347Z
Not the transcendence of $\pi$ but rather the transcendence of the formal power series analogue over a finite field.  I can't tell you what to read in the book because the pandemic makes it impossible for me to access a copy currently.
Jeffrey Shallit
CC BY-SA 4.0
2020-08-22T12:24:48.597Z
Have you found access in the mean time to your copy?
Jori
CC BY-SA 3.0
2016-07-25T10:55:52.133Z
2016-07-25T10:55:52.133Z
Jeffrey Shallit
<p>In many textbooks the Chomsky-Schützenberger enumeration theorem is stated as that the characteristic formal power series of a language is $\mathbb N$-algebraic, if the grammar is unambigious. In some other books the formulation is given, that the structure describing function $$f_L(x)=\sum_{n \in \mathbb N}l_nx^n$$ is algebraic over $\mathbb Q$ iff the grammar is unambigious, where $l_n = \vert \Sigma^n \cap L \vert$.
I understand that by replacing every terminal by the same terminal in the system of equations associated with a grammar $G$ it is possible, to obtain the structure describing function, but I couldn't find a proof anywhere,(and don't know how I could construct one)  that then the (analytical) power series $f_L(x)$ is not transcendental. </p>

<algebra><grammars>
Chomsky Schützenberger enumeration theorem
Christian Hagemeier
# Chomsky Schützenberger enumeration theorem

(Asked by: username_0 on 2016-07-23)

In many textbooks the Chomsky-Schützenberger enumeration theorem is stated as that the characteristic formal power series of a language is $\mathbb N$-algebraic, if the grammar is unambigious. In some other books the formulation is given, that the structure describing function $$f\_L(x)=\sum\_{n \in \mathbb N}l\_nx^n$$ is algebraic over $\mathbb Q$ iff the grammar is unambigious, where $l\_n = \vert \Sigma^n \cap L \vert$.
I understand that by replacing every terminal by the same terminal in the system of equations associated with a grammar $G$ it is possible, to obtain the structure describing function, but I couldn't find a proof anywhere,(and don't know how I could construct one) that then the (analytical) power series $f\_L(x)$ is not transcendental.

**Tags:** algebra, grammars


---

## 1 answers

### Answer by username_1 on 2016-07-25. Score: 10 | Accepted answer

There is a proof in the book of Kuich & Salomaa, *Semirings, Automata, Languages* and another one in the paper of Panholzer, "Gröbner Bases and the Defining Polynomial of a Context-free Grammar Generating Function", J. of Automata, Languages and Combinatorics **10** (2005), 79–97. I wish there were a simple and clear proof of the result.

> **Comments:**
> **username_2**: But it's called _Chomsky-Schützenberger_ enumeration theorem; shouldn't there be a proof in their _Algebraic theory of context-free languages_ (Studies in Logic and the Foundations of Mathematic), which seems very accessible? However, I quickly looked through it but I couldn't find an explicit statement there (let alone a proof). If it isn't there, then the question rises where the name comes from...  
> **username_1**: It is named for them because they had the basic statement and idea in their paper, although they did not supply a complete formal proof.    That is not unusual in mathematics.  
> **username_2**: Oh I see, no that isn't at all uncommon. But how big is the gap between the ideas that Chomky and Schützenberger provide and the actual proof? Because from casual glancing both Kuich&Salomaa and Panholzer need quite a bit of machinery to get there (I don't know how much because there is no explicitly delineated proof in those either, as far as I can tell). How much of the Kuich-Salomaa book do you need?  
> **username_1**: The ingredient that is needed is some guarantee that when you take an unambiguous CFG and convert it to a system of algebraic equations in the almost-trivial way described by Chomsky and Schützenberger, that there indeed exists a solution to this system in power series, and that it is unique.  
> **username_2**: So what would I need to read in the Kuich-Salomaa book? I'm a logician, so this is not really my topic, but I've always wanted to learn about this proof; I remember reading that the transcendence of $\pi$ was equivalent to some language being inherently ambiguous and found that quite neat, although I'm not sure I remember the details correctly.  
> **username_1**: Not the transcendence of $\pi$ but rather the transcendence of the formal power series analogue over a finite field.  I can't tell you what to read in the book because the pandemic makes it impossible for me to access a copy currently.  
> **username_2**: Have you found access in the mean time to your copy?  

---

