Leoni G., Sprugnoli R. Some relations between Markov algorithms and formal languages. In: Calcolo, vol. 13 pp. 261 - 284. Giardini, 1977. |

Abstract (English) |
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. | |

Subject |

1) Download Document PDF |

Open access Restricted Private