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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
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.
-
$\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$– JoriCommented Jul 26, 2020 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$ Commented Jul 27, 2020 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$– JoriCommented Jul 27, 2020 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$ Commented Jul 28, 2020 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$– JoriCommented Jul 28, 2020 at 19:39