自然语言理解(App)习题参考答案

No.95,ZhongguancunEastRoadBeijing100080,China:[phone](App)[e-mail](1)Timeflieslikeanarrow.(a)(b)(2)Hedrewonecard.(a)(b)(3)(a)(b)NLPR,CASIA2004-3-63NLPR1-2.(1)IamstudyinginPekingUniversity.(2)Heputabookonthedeskintheleftroomofthethirdfloor.NLPR,CASIA2004-3-64NLPR1-3.(1)(2)LRLR(3)1-4.NLPR,CASIA2004-3-65NLPR2-1.Xxp(x)=P(X=x)x∈XXH(X))(log)()(2xpxpXHXx∑∈−=NLPR,CASIA2004-3-66NLPR2-2.KLp(x)q(x)KL(Kullback-Leibler))()(log)()||(xqxpxpqpDXx∑∈=NLPR,CASIA2004-3-67NLPR2-3.pqKLD(p||q)≠D(q||p)NLPR,CASIA2004-3-68NLPR2-4.X~p(x)q(x)p(x)p(x)q(x)H(p,q)=H(p)+D(p||q)∑−=xxqxpqpH)(log)(),()()(log)()()||()(),(xqxpxppHqpDpHqpHXx∑∈+=+=))(log)((log)()(log)(xqxpxpxpxpXxXx−+−=∑∑∈∈∑∈−=Xxxqxp)(log)(NLPR,CASIA2004-3-69NLPR3-1.(a)010,1(b){a1a2…anan…a2a1|ai∈{0,1},1≤i≤n}:(a)G=({A,B,S},{0,1},S,P)P:SJ0B|1AAJ0S|1AA|0BJ1S|0BB|1(b)G=({A,S},{0,1},S,P)P:SJ0A0|1A1AJ0A0|1A1|εNLPR,CASIA2004-3-610NLPR3-2.G=({S,B,C},{a,b,c},P,S),P:S→aSBC|abCCB→BCbB→bbbC→bccC→ccL(G)=?S⇒aSBC⇒aaSBCBC⇒aaabCBCBC⇒a3bCBCBC⇒a3bBCCBC⇒a3bbCCBC⇒a3bbCBCC⇒a3bbBCCC⇒a3bbbCCC⇒a3b3cCC⇒a3b3ccC⇒a3b3c3……L(G)={anbncn|n≥1}NLPR,CASIA2004-3-611NLPR3-3.GS→ABA→Aa|bBB→a|Sb:(1)baabaab(2)bBABb(1)SABaAbBabSABabBa(2)NLPR,CASIA2004-3-612NLPR3-4.PDAPDA3-5.GGNLPR,CASIA2004-3-613NLPRThanks