Istituto di Scienza e Tecnologie dell'Informazione     
Leoni G., Sprugnoli R. Some relations between Markov algorithms and formal languages. In: Calcolo, vol. 13 pp. 261 - 284. Giardini, 1977.
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, subc1ass 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 strong LL (k) grammar, it is possible to produce automatical1y a pointer Markov algorithm parsing the language generated by the grammar. These constructions are particular1y interesting because pointer Markov algorithms can be compiled conveniently into machine code programs.

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional