Markov algorithms have received very little attention in the studies about formal languages, so the purpose of the present paper is twofold: i) to characterize languages in terms of Markov algorithms, and ii) to produce automatically Markov algorithms accepting or parsing languages generated by given grammars.

We use a particular, although universal, subclass of Markov algorithms, which we call “pointer Markov algorithms»; we obtain a characterization of: i) regular, ii) deterministic context-free, and iii) type O languages, which is quite «natural» in terms of these algorithms. Furthermore, we show that, given a right linear or a strongLL(k) grammar, it is possible to produce automatically a pointer Markov algorithm parsing the language generated by the grammar. These constructions are particularly interesting because pointer Markov algorithms can be compiled conveniently into machine code programs.

In the study of fundamental properties of algorithms, attention is often given to classes of abstract general procedures. Of these, the Markov algorithm has some claims to favour owing to the simplicity of its semantics, the relative power of its basic operations and its independence of numerical concepts. Such a study will generally be assisted by some practical experience in using the methods introduced.

The Markov algorithm [1, 2] can be used as a language parser and as means fordefining languages [2–5]. This work is concerned with the amount of computing time which the algorithm requires. Computing time is measured by the number of comparisons between the rules of the grammar and the input string. A modification is introduced into the algorithm which reduces the computation time. It is proved that under certain conditions imposed on the rules of the grammar the computing time required by the modified algorithm is bounded linearly by the length of the input string. One set of such conditions requires that each application of a grammar rule reduces the length of the input string. Another set requires that each application does not increase the length of the input string and that the graph associated with the rules of the grammar satisfies certain restrictions.