Bounded Push Down Automata
Branislav Rovan · Kybernetika · 1969
The central problem of the theory of grammars and languages is that of determin ing for a given class S of languages a class of which accept exactly the languages in S. This problem was solved for regular events [ l ] , linear languages [2], context-free languages [3], [4] and context-sensitive languages [5]. In this paper we are going to introducea utomata (the so called push down automata bpda) which accept bounded languages, defined and studied in [6]. By this one of the Ginsburg's open problems [7] is solved. The basic ideas and notations of the theory of context-free languages are used just in the sense of those in [7]. From [7] is also the definition of bounded language: