随机文法举例

例1：一个随机上下文无关文法GS=(VN, VT, PS, S)，其中VN={S}，VT={a, b}，生成式PS：SaSb,Sab p1p对于{S->βj}j=1,2,有pijp1p1

j1233可生成的一个字符串：SaSbaaSbbaaabbbab pp1p此时：p(x=a3b3)=pp(1-p)=p2(1-p)

推广：由GS产生atbt，t≥1的字符串的概率是pt-1(1-p)，由此的随机语言为：L(GS)={(atbt, pt-1(1-p))| t≥1)

ppp例2：随机文法同上，但生成式PS改为：SaS,Sb,Sab，

123则生成式x=ab有多条生成路径：

pab，此时生成概率p(x=ab) = p3 (1) S3ppaSab，此时生成概率p(x=ab) = p1p2 (2) S12

例3：一个等边三角形和它的8个有畸变或受噪声干扰的三角形以及其基元如图，每一个三角形都用三个字符的句子来描述。

按先验知识，这9个不同的三角形的生成概率如下表：

x x1=ab1c1 x2=ab1c2 x3=ab1c3 x4=ab2c1 x5=ab2c2

设产生字符串的随机有限态文法是GS=(VN, VT, PS, S)，其中VN={S, A1, A2, A3, A4}，VT={a, b1, b2, b3, c1, c2, c3}，生成式P：

pppp(1) Sb1A2，(3) A1b2A3，(4) A1b3A4，aA11，(2) A12p(x) 1/36 2/36 3/36 1/36 21/36 x x6=ab2c3 x7=ab3c1 x8=ab3c2 x9=ab3c3 p(x) 2/36 3/36 2/36 1/36 34pppp(5) A2c1， c1，(6) A2c3，(8) A3c2，(7) A25678pppp(9) A3c2，c2，(10) A3c3，(11) A4c1，(12) A49101112p(13) A4c3

13求每一生成式的概率pi，i=1,2,…,13

使概率规范化的条件为：p1=1，p2+p3+p4=1，p5+p6+p7=1，p8+p9+p10=1，

p11+p12+p13=1

由产生字符串x1=ab1c1的先验概率p(x1)=1/36，得p(x1)=p1p2p5=1/36 同理：p(x2)=p1p2p6=2/36，p(x3)=p1p2p7=3/36，p(x4)=p1p3p8=1/36，

p(x5)=p1p3p9=21/36，p(x6)=p1p3p10=2/36，p(x7)=p1p4p11=3/36， p(x8)=p1p4p12=2/36，p(x9)=p1p3p13=1/36

解上述方程可得：p1=1，p2=1/6，p3=2/3，p4=1/6，p5=1/6，p6=1/3，

p7=1/2，p8=1/24，p9=21/24，p10=1/12，p11=1/2，p12=1/3，p13=1/6

从而得到每一生成式的概率。