A representation theorem of infinite dimensional algebras and applications to language theory

Abstract

We assign to each c.f. grammar G an infinite dimensionale algebra A_{R}(G) over a semiring R. From a representation \varphi of A_{R}(G) in R<Z^{(*)}<, when Z^{(*)} is a certain polycyclic monoid, we derive easily the theorems of Shamir-Nivat-Salomaa, Chomsky-Schützenberger, Greibach about a hardest c.f. languages and Greibach N.F. LL(k) und LR(k) languages get an easy algebraic characterisation, which generalises to non deterministic LL and LR-languages, which are linear in time and space too.