没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记53(2002)网址:http://www.elsevier.nl/locate/entcs/volume53.html12页类比与形式语言YvesLepage1;2ATR口语翻译研究实验室619-0288K你好, 我是潘摘要在本文中,我们主张研究符号串之间的类比。 我们展示了一些字符串集,即,某些形式语言的特点是使用类比。 我们认为,一些初步的“好的性质”可能会恳求赞成使用类比的研究中的形式语言与自然语言的关系。1介绍在语言学中,洪堡、赫尔曼·保罗、鲍登·德·库特奈和索绪尔认为,类比是一种认知过程,在给定一个词的两种形式和第二个词的一种形式的情况下,人们创造出一个词,missinggform:o<$ra<$to<$rem:o<$ra<$tor=hono<$rem:x )x=honor(analogi-cal方程)。符号串之间的这种类比,通常记为A:B = C:D,将四个符号串放入“比例”中。 它们似乎独立于任何特定的语言,并且至少在符号水平上,求解这些方程的能力被认为是一种自动化过程和普遍能力[5]。我们将只关注符号层面上的类比,而不直接关注像胳膊:手=腿:脚这样的类比。此外,我们也不关心像原子就像太阳系这样的句子,它们之所以被不恰当地称为类比,正是因为它们建立在类比的基础上(这里:电子对于原子核就像行星对于太阳一样,见[3])。1感谢教授博伊特阅读这篇论文的草稿此外,感谢匿名裁判谁指出了许多不完善和错误。 所有的错误都是我的。2电子邮件:yves. atr.co.jpc2002年由Elsevier Science B出版诉在CC BY-NC-ND许可下开放访问。LePage22类比2.1示例所以我们只考虑象征层面的类比让我们用一些与我们打算处理的类比类型无关的情况来澄清::g6 =:Wabc:ac6=acb:aca:b 6=c:dwalk:walkd6=go:wentbird:wings 6=fish:finsabc:ac 6=ca:anything第一行表明符号不能被分解:在我们看来,这是不可能的。第二条线表明,对于我们来说,类比首先与符号有关,只有在第二步中才与秩序有关,因此在这种情况下,对我们来说有效的类比是:abc:ac=acb:ab。以下三行表明,在给定的范围之外,不考虑任何进一步的信息:解析算法不应具有关于字母顺序的知识,也不应具有英语变位知识,也不应具有关于动物形态学的知识。最后一行和许多其他类似的行表明,如果第一个字符串(这里是b)的单个符号既不属于第二个字符串也不属于第三个字符串,那么就没有任何类比可以成立,因此下面的类比方程没有任何意义:abc:ac=ca:x。现在,我们认为以下例子是有效的类比。 虽然第三个问题产生了一种野蛮(goed),但它是逻辑方程walk:walked=go:x的精确解(见[15])。最后一个证明了类比方程可能有多个解。因此,一般来说,一个给定的类比方程可能没有解,唯一的解决方案,或几个解决方案。g:4g=w:x)的方式x=4w看:看=走:x)x =走:走=走:x)x =走寓言:神话般的=奇迹:x)x =奇迹般的ab:aabb=aaaabbbb:x )x =aaaaabbbbbaba:aa=cbcbcbc:x)x =cbcbc_x= cbcbc_x= cbcccLePage342.2形式化从一般性质开始,亚里士多德(Nicomachian伦理学)以及赫尔曼·保罗(Hermann Paul)[13,chap. V.,x76,p.107]当他们执行所谓的手段交换时,使用常识:A:B = C:D,A:C =B:D。另一个属性,依赖于相等的对称性,也被亚里士多德使用:A:B= C:D,C:D=A:B。这两个性质被视为公理,导致同一类比的其他五种等价形式,因此人们可以给出下面的定理,这对获得进一步的定理是有用的。证明是微不足道的。定理2.1下列八个类比是等价的:A :B=C:DA: C= B: D(手段交换)B: A= D: C(比例倒置)B :D=A:CC:A=D:BC: D= A: B(对称性)D: B= C: A(交换极端)D: C= B: A(读数对称)2.2.1相似性和距离在考察了符号串之间的一系列类比之后,我们证明,如果A中的一个符号既不出现在B中,也不出现在C中,则类比方程A:B=C:x的解不存在(见2.1)。通过逆置,为了使解存在,A中的任何符号都应该出现在B或C中,或者同时出现在两者中,这样就可以提出下面的公理公理1设V是一个字母表。8(A; B; C; D)2(V);A:B = C:D)AB[C当考虑符号的顺序时,这也应该成立,因此,一般来说,类比不会重新排列字符串的任何组成部分因此,A的长度小于或等于它与B和C的相似性之和,其中两个符号串A和B之间的相似性(A; B)被定义为它们的最长公共子序列的长度43我们称V为符号集,V为用V的元素构建的字符串集。 在该序列中,(A;B;C;D)2(V)4。并不意味着测试A中的不同系统的设置。[4]回想一下子序列不一定是连通的。比如说,(ababababa; aaababa)= 5,或(triangle; angularity)= 4。LePage44公理2设V是一个字母表。8(A; B; C; D)2(V);A:B = C:D)jAj(A; B)+( A; C)如果A的长度小于这个总和,这意味着A中的某些符号也以相同的顺序出现在B和C中,因此也出现在D中,因为它们必须以相同的顺序复制到类比方程的解让我们称(A; B; C; D)为这些符号出现的次数一个得到:A:B = C:D )j A j =(A; B)+(A; C)(A; B; C; D)通过应用定理2.1,可以得到七个这样的等式:j A j =(A; C)+(A; B)(A; C; B; D)j B j =(B; A)+(B; D)(B; A; D; C)j B j =(B; D)+(B; A)(B; D; A; C)j C j = (C; A)+ (C; D)(C; A; B; D)j C j = (C; D)+ (C; A)(C; D; A; B)j D j =(D; B)+ (D; C)(D; B; C; A)j D j =(D; C)+(D; B)(D; C; B; A)所有的8>jA j=(A;B) +(A;C)(A;B;C;D)>>jB j=(B;A) +(B;D)(A;B;C;D)j C j = (C; A)+ (C; D)(A; B; C; D):>个这很容易导致下面的引理:2.2V是一个很好的选择。8(A;B;C;D)2(V)4;A: B= C:D)8>jAj (A;B)=jCj (C;D)(1)>>jBj (B;D)= jAj (A;C)(2)j C j(C; A)= j Dj ( D; B)(3)>jDj ( D; C)= j Bj ( B; A)(4):>个把线(1)和线(4)相加,并利用相似性的对称性,我们就可以得到下面的显著结果,即极值长度和均值长度之和相等。>j D j = (D; B)+ (D; C)(A;LePage542引理2.3设V是一个字母表。8(A; B; C; D)2(V);A:B= C:D)jAj + j Dj = j Bj+ j Cj由于前面的结果,在这个框架中没有一般重复的地方。 一般的重叠会使我们写下:设V是字母表。8(A; B)2(V);A:B= AA:BB但这是相反的,证明了这个引理。对于考试项目, :bm =a2n :b2m,将意味着n+2 m = 2 n + m,这是可能的,当且仅当n = m。 5前面的结果可以在以下符号串之间的类比的(部分)特征化中收集,其中D仅出现在等式的左侧,并且右侧仅包含A,B和C。理论2.4让V成为一个教唆犯。8(A;B;C;D)2(V)4;8>A:B=C:D)><(B; D)= jA j + j B j +(A; C)(C; D)=j Aj + j Cj +( A;B)j Dj =j Aj + j Bj + j Cj>(A; B; C; D)=jA j +(A; B)+(A; C)再加上一个约束,这个特征直接导致了一个算法的实现,用于解决和验证类比方程。然而,这个部分的刻画对于本文的后续部分是足够的,以便我们证明其他一些形式结果。众所周知,相似性与特定的字符串距离[10]有关,为了遵循[18]的术语,我们称之为编辑距离,p. 406命题2.5设V是符号的字母表,设是字符串之间的相似性,设V是编辑距离。8(A;B)2(V)2;n(A;B)=jAj+ jBj 2(A;B)在定理2.4中,用距离代替相似性,我们得到了前面类比刻画的一种更直观的形式[5]事实上,“纯类比”和“重叠类比”似乎6取代是通过应用删除,然后插入,或插入,由于删除而失败。 对 于 初 始 化 , 编 辑 (edit;edition) =3(插入三 个字符串:i ,o 和n), 编 辑(triangle;angularity)=10(删除t,r,i,插入u,删除e,插入a,r,i,t,y)。 编辑距离是一个度量,因为它验证了恒等式、对称性和三角不等式这三个公理。LePage644>=6PPPPPi/PPPBCQPP?PiPPPPPPPqP=PD?6符号之间的理论2.6让V成为一个教唆犯。8(A;B;C;D)2(V)4;>8(A;B)=(C;D)>>A:B=C:D)>(A;C)=jAj + j Dj = j Bj + j Cj1(A; B; C; D)=4>>>(jAj + j Bj + j Cj + j Dj(A;B)(C)(B;D)(C;D))>:系统的前三个等式可以在下图中直观地看到:一2.2.2邻接和级联关于类比的直觉是,如果两个类比没有任何共同的符号,它们总是可以连接的事实上,有三种可能的连接方式符合直觉。然而,对于mally,连接不是唯一的可能性。人们可能会混淆sym-bab,例如:“:a=bb:bab。我们将拒绝这种可能性。公 理3设V是al phabet,且V1V 、V 2V ,这样在 V1\V2 处 的 h =;,8(A1;B1;C1;D1)2(V1 );8(A2;B2;C2;D2)2(V 2 )这样,A1:B1=C1:D1和A2:B2=C2:D2我们假设只有三种可能的方式连接类比8A1A2:B1B2=C1C2:D1D2>A1A2:B1B2=C2C1:D2D1>:A1A2:B2B1=C2C1:D1D2LePage7因此,“:a=bb:bab对我们来说不再是一个有效的类比前面的公理意味着类比方程只有两种可能的解:“:a=bb:x) x=abb_x= bba ,因此,类比方程ab:aabb=aabb:x具有aaabbb作为唯一LePage8MMM0M解决方案,而aababb不是解决方案。前面的公理在定理4.1和4.2的证明中是必要的。3形式语言在研究了符号串之间的类比,并假设和推导了一些形式化的结果之后,我们现在可以转向使用类比来构造符号串的集合了3.1直接类比推导我们首先介绍直接类比推导。定义3.1设V为字母表。 直接类比导数,注记,模V ,whehoselements(v;v0)arenotedv!v0,定义为:8(w;w0)2VV;w`w0,9V! v0 2M=w:w0 =v:v0虽然我们使用的符号! 对于M的元素,它不应该以它在经典重写系统中的方式来解释。 这个表示法只是为了与格-马的经典表示法进行比较,在格-马的经典表示法中,M的元素被称为规则。然而,这里的意义是不同的。在标准规则下,w与v精确匹配以生成,在第二步中,w0。你好,这是我们的成果在相同的时间内,在新的时间(不是w)“match s“w和v 0 t上执行。3.2类比语言我们现在展示一些语言,即。符号串的某些集合可以用基于类比的设备来构造定义3.2设V为字母表。设AV和MV V,两者都成立。分析逻辑环(A;M)的语言定义如下:+(A;M)=A [fw0 2V j 9w2A=w`wg与”他说。+“M,直接类比推理的反分析封闭性前面的定义符合形式语言的通常表示。它的目的是生成一种语言。因此,像往常一样,标准结构归纳法被用来生成类比字符串语言的所有成员。从A的元素开始,应用与M的元素作为模型的所有可能的类比LePage9生成的相互问题就是承认的问题 在类比系统中,一个给定的字符串的语法性,即。在使用模型集类推地约简给定字符串之后,针对该语言的已证实字符串集来测试其在语言中的成员对于识别,M对中的字符串在它们出现在M中的相反方向上使用,并且类比在与生成方向相反的方向上求解由于定理2.1中比率的反变换,这是可能的.因此,类比字符串(A ; M)的语言的“语言学“关系如下:A是证明字符串的集合,即,,字符串的集合,语言的任何候选元素都将与之进行精细比较; M是聚合模型的集合(变格,共轭,形态派生,句法转换等)。),根据该方法,语言的任何候选元素都可以通过类推来减少74类比语言在哪里?我们现在将从自然语言类的角度简要地考虑类比语言与自然语言研究的相关性。4.1语言的例子通过归纳和使用公理3,可以证明以下三种著名的正则语言、上下文无关语言和上下文相关语言都是类比字符串语言fan =n1 g =(fa g;fa!(aag)fanbn =n1 g =(fabg;fab!aabbg)fanbncn =n1 g =(fabc g;fabc!aabbccg)更一般地说定理4.1anan: :an= n1g =(faa:::ag;f(a a:a!a2a2: a2)g)12m12m12m12mProof. Fo r fan=n1g.Completeness:(fag;fa! aag)fan=n1g. 重新计算这两个字符串中的差分符号集。我的天啊! aa g)。这是itisequivalentto:a`w. 因此,存在序列w1,w2,7r e d u c e这个词的意思是减少到一个正常的形式,而不是在这个意义上的字符串将变得更短。LePage10... ,wn 这是因为在下面的数组中没有列。a:w1= a:aa ,w1:a = aa:a)w1 a[aa = fag w1:w2= a:aa,w2:w1= aa:a)w2w1[aa...wn :w=a:aa,w:wn =aa:a)wwn[aa数组中的第二列是通过比率的反转获得的;第三列是公理1的应用。 这最后一列暗示:w fa g,which的意思是wis ofthetypean。Con si sten cy:fan=n1 g(fa g;fa! aa g)。通过推导,通过具有f(fag;fa!aa g)。 Base:fag(fa g;fa! aa g)通过对一个 逻 辑 序 列 的 定 义 。 提 示 : suppposethatan我 是 一 个 emberof(fag;fa! aag ) 。 一 个 逻 辑 方 程 a 的 唯 一 解 x : aa=an: x是an+12fan=n1g。Fo r fanbn=n1g。Completeness:( fabg;fab !aabbg )fanbn=n1g. 一个与eab上的任何一个类似的推理给出了sw2fanbn=n1g)wfa;b g。根据归纳法,根据公理3,所有的a都是b的一部分 其中hn必须等于m。Con sisten cy:fanbn=n1 g(fab g;fab! aabbg)。 我不知道。Base:ab2(fabg;fab! aabbg)是真实的,通过对分析语言的定义。Induction:supposethatanbn 它是一个嵌入式的(fabg;fab! aabb g)。Becausea:aa=an :an+1b:bb=bn :bn+1是真 类 比 , 根 据 公 理 3 , 类 比 方 程 nab : aabb=anbn 的 唯 一 解 x: x是an+1bn+12fanbn=n1g。对于fanbncn=n1g。这是一个简单的公式,通过计算,abc: aabbcc=anbncn :an+1bn+1cn+1intoab:aabb=anbn :an+1bn+1 c:cc=cn :cn+1 什么时候吃的。Identicalratiosprovetan: an=n1gisalanguag eof类比字符串12m2因此,用类比字符串语言表示,正则语言、上下文无关语言和上下文相关语言的三个著名例子非常简单(只有一个证明字符串和一个推导规则),而且幸运的是,它们是绝对相似的。LePage11使用与上述定理类似的证明,很容易证明:定理4.2fambncmdn =n1^m1 g =(fabcdg;fabcd!abbcdd;abcd!aabccdg)LePage12这种上下文敏感的语言,因此也是一种类比字符串的语言,是反对自然语言上下文无关性的两个著名反例的基础:在Bambara的形态学[1]中,以及在瑞士德语苏黎世方言的句法中[17]。 值得注意的是,作为一种类比字符串语言,这种语言相当简单。因此,一些上下文敏感语言是类比字符串的语言问题是:这是否走得太远了?4.2不断增长在[7]中提出了轻度上下文敏感性来表征适合自然语言的语言家族(大于上下文无关,但严格小于上下文敏感),并且在[8]中提出了其中一个性质,常数增长,比半线性弱([12]最近驳斥了自然语言是半线性的):定义4.3语言L具有常数增长性质,当(且仅当)当以长度递增的顺序排列语言的字符串时两个连续的长度不会相差任意大的量。现在,可以使用引理2.3证明:定理4.4任何类比字符串的语言都验证了常数增长性质。证据 设(A; M)是一种类比串语言。让我们称kA为所有jwj的最大值,其中w在A中。A存在,因为A是有限的。 让我们称k M为所有j v 0j v j上的最大值,v! v 0在M. kM也存在,因为M也有限。(A; M)是由归纳产生的,从A的元素开始,通过应用M的元素的直接类比推导。在生成开始时,集合A具有常数增长属性,其中kA是两个连续长度之间的量的可能(太大)界限假设在归纳生成的某个步骤中,在该步骤之前创建的所有字符串的生成集具有常数增长属性。在下一步中,将在元素的帮助下生成一个新的字符串在最后一步中获得的实际上,零个、一个或几个8元素w0可以在任何元素v的 帮 助 下 生 成! v 0的M,取决于类比v:v 0= w:x是否有零个,一个或多个解决方案。当至少存在一个这样的解w0时,引理2.3告诉我们,jvj + jw 0j = jv 0j + jwj,因此jw 0jwj = jv 0j jvj。如果jw 0j jwj0,则长度减小,并且j w 0j可以被布置在8公理1和引理2.3意味着一个类比方程有有限个解。LePage13M所有已完成的语言元素定义,并且可能比A. 如果j w0j j w j > 0,则长度增加,但小于k。由于这对于在新步骤期间生成的所有新串w0都是真实的,因此,所生成的串的新集合联合所生成的串的集合,直到该步骤具有连续的增长,其中hk=maxx(kA;kM)是以递增顺序布置的两个连续串长度之间的量的界限这就结束了归纳法的证明。2因此,像fa2n=n2INg这样的语言不是代数字符串的语言,因为它不具有有界增长性质。 幸运的是,一些“非自然”语言是类比字符串语言所无法达到的。结论只有少数人提出了类比模式化的建议,这可能是因为多年来语言学的主流,生成语言学,反对现代语言学创始人的作品(例如,[13,chap.五十二]或[15,第三部分,章。 4 &5]),明确反驳类比作为一个可能的研究对象(见[6,132和136],从乔姆斯基报价)。然而,根据其他论点[5],类比可以被认为是语言的一个组成部分(当然,肯定不是唯一的一个)。我们已经展示了如何生成一族形式语言,称为类比字符串语言。重要的是要注意,它们的构造,就像简单上下文语法[4]的情况一样,不使用任何非终结符。在根据一些模型进行约简之后,针对一些已证明的字符串简单地测试语法性自然语言中已经提倡通过还原到已证实的形式的计量处理[14]。针对自然语言的无文本的语义假设,很容易证明关键语言anbmcndm=n1 g是一种类比串语言。此外,所有类比字符串的语言都具有不断增长的特性,这部分地干预了温和的上下文敏感性,这是一个为了应对人类语言的明显力量而引入的引用[1] Culy、C. ,Bambara,LinguisticsandPhilosophy8(1985),pp.第345-351页。[2] D owt y,D. ,L. 卡尔图宁 和A. Zwicky编辑,“Naturallanguageprocessing”,剑桥大学出版社,剑桥,1985年。LePage14[3] Gentner,D. 李文,《结构映射:一种模拟的理论模型》,《计算机科学》第7期(1983),第100页。155-170[4] 伊利湖,“O n A mbiguit y in I nt e r n a l C o nt e xtu a l L a ngu a g e s,“in[11],1998,pp. 29-45.[5] 它是一个N,E。,概念,类比和通用语法,物理学杂志22(1994),pp.37比53[6] 它是一个N,E。 和J。Haukioja,131-177。[7] 乔希,A. ,“Treeadjoininggramarars:需要多少个文本来提供合理的结构描述?”在[2],1985,pp.206- 250[8] 乔希,A. ,K. 用Y型刀和D. Weir,31比81[9] Ke rtesz,A. ,《科学理论与语言学》,PeterLang,法兰克福,1997年。[10] 莱文施泰因湾1966年苏联物理学报第10卷第10期第11页第12页第13页第14页第15页第16页第17页第18页第19页第1 707-710[11] 马丁·维德,C. 、如果是,and《 自然语言的计算分析》,约翰·本杰明出版公司,阿姆斯特丹1998年,费城[12] Michaelis,J. 和M. Kr acht,“LogicalAspecctsofCoinputalLinguistics,“Number1328inLNCS/LNAI,SpringerVerlag,Berlin,1997,329-345pp.[13] Paul,H. ,1st ed.1880年]。http://www.gutenberg.aol.de/paulh/prinzip/paul vorr.htm[14] S ager,N. ,“NaturalLannguageInformationProcessing:AComputerGrammarofEnglishandItsApplications,”Addison-Wesley,Reading,Mass.,1981.[15] 是个大麻烦,弗。,1916年]。[16] 塞尔斯山口、S.Shieber和T.Wasow,editors,“FoundationaLIssuesinaturallanguageprocessing,”MITPress,Cambridge,1991.[17] Shieber,S. M. 《语言学与哲学》第8期(1985年),第110-111页。333-343.[18] Stephen,G. A. ,
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功