随机正则文法的相似

对于给定的随机正则文法G_8是否存在着一个真正随机正则文法G_8,使得L(G_8)=L(G_8),若存在,又如何求出G_8?本文在两个不同的但都不是十分严格的限制下,证明了Thompson方法是有效的,它不仅提供了一个从G_8求G_(?)的方法,而且还包括判断这样的G_8是否存在的判别准则,在此基础上,本文将随机文法等价的概念推广,提出了随机文法相似的概念,并证明了在受到上述相同限制的前提下,每一个随机正则文法G_8总有一个与之相似的真正随机正则文法G_8,其中相似系数由G_8本身唯一决定。

On the Similarity of Stochastic Regular Grammars

In this paper,we prove that in an extensive range the Tompson method is valid.That is,the method is not only a tool for determining G_s according to G_s bub also a principle for deciding whether or not such G_s,exists.Based on this,to generalize the concept of the equivalence of stochastic regular grammars we introduce the definition of the similarity of stochastic regular grammars.And we prove that in the same range for each stochastic regular grammar G_s there exists a real stochastic regular grammar G_s,such that G_s and G_s are similar,where the parameter depends only on G_s,itself.