Markov Chains Connected to the Process of Generation of the Words by a Generative System


Gabriel V. Orman




In this paper we considered the process of generation of the words from a stochastic point of view. One of the generative systems constituting the Chomsky hierarchy in the Theory of Formal Languages , namely the so-called phrase-structure grammar, is taken into consideration. The random variable giving the number of derivations by which a word can be generated is introduced and its characteristics are determined. Also, the problem of Markov dependence is discussed and a new procedure for generating the words is proposed.