On the Power of Subroutines for Finite State Machines
Markus E. Nebel · 2001
In this paper we extend the finite state machines by a subroutine concept. Two implementations are considered. The first implementation yields a new class of languages which is a subclass of the context-free languages. The second one leads to an alternative automata-model for the context-free languages. Besides the generative capacity other properties like determinism, reversal languages, etc. are also studied. We prove that determinism for the second implementation is equivalent to the notion of $LL(1)$-languages. The motivation for those observations comes from a description language for plot data called DPF which is used in practice and which possesses simple non-regular constructions only.