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.