Random Phenomena and Some Systems Generating Words


Gabriel V. Orman




The process of the generation of words by a generative system is considered from a stochastic point of view involving Markov chains. Because the sequences of intermediate words (called derivations ) by which the words are generated are finite, it results that finite Markov chain: will be connected to the process. In this paper a very general generative system from those constituting: the Chomsky hierarchy is considered, frequently called a phrase-structure grammar. In Section 1 the basic definitions and notations relating to this type of generative system and some notions relating to Markov chains are given, according to (3) and (4) . Then, the random variable giving the number of derivations by which a cord can be generated is defined and its characteristic are determined according to (9) . Finally a new procedure to generate words is introduced and the property of invariance of the transition matrix is established: also a problem of the "reflecting harriers" type is discussed.