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

摘要

The algebraic theory we present here continues the earlier work of several authors. The leading idea is to develop a machine and production free language theory. The interest in such a theory is supported by the hope that the proofs in such a theory need fewer case discussions, which often lead to errors, and that a view which is free from nonessentials of language theory will lead to a progress in the direction of our problems. Even if the theory is in an early stage, the attempt pays out in a machine free definition of LL(k) and LR(k) languages, which leads easily to generalizations of non-deterministic LL(k) and LR(k) languages with the same space and time complexity behaviour. Furthermore, we are able to show that this theory is not restricted to the context-free languages but also applies to the whole Chomsky hierarchy. Our theory is in a sense dual to the theory of formal power series as introduced by M. Schützenberger.