9
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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... $\endgroup$ – Jori Jul 26 '20 at 15:42
  • 1
    $\begingroup$ 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. $\endgroup$ – Jeffrey Shallit Jul 27 '20 at 16:04
  • 1
    $\begingroup$ 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? $\endgroup$ – Jori Jul 27 '20 at 17:28
  • $\begingroup$ 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. $\endgroup$ – Jeffrey Shallit Jul 28 '20 at 18:48
  • $\begingroup$ 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. $\endgroup$ – Jori Jul 28 '20 at 19:39

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.