Truncations of infinite matrices and algebraic series associated with some CF grammars (Q1079959)

The author considers an algebraic system over \({\mathbb{R}}[x]\) of the form \(X=a_ 0(x)X^ k+a_{k-1}(x)X+a_ k(x)\), where \(a_ 0(x)\) and \(a_ k(x)\) are in x\({\mathbb{R}}[x]\) and \(a_{k-1}(x)\) in x\({\mathbb{R}}\). Using this system, an infinite-state automaton and its incidence matrix A are introduced, via Kuich's results. Let \(A_ n\) denote the \(n\times n\) northwest corner truncation of A; the author proves that the eigenvalues of the \(A_ n\) are dense in some algebraic curves. Then a new result on positive algebraic series is obtained, when the coefficients of \(a_ i(x)\) \((i=0,...,k-1,k)\) are positive. Viewing the algebraic series generated by the system as a function in the complex variable x, the author proves, using the above result on truncations, that the radius of convergence equals the least positive zero of the modified discriminant of the system. Finally, applications to context-free languages are described. The author obtains a procedure for calculating the entropy of some one-counter languages, obtaining new results along the lines of those due to Chomsky, Miller and Kuich, and he performs an asymptotic analysis of the number of grammatical strings of a given length. Other applications to Dyck and Łukasiewicz languages are also considered.