自然语言是不是正则语言?

gugu&gigi 发布于 12/07 13:46
阅读 92
收藏 0

如题。

加载中
0
韦小仇
韦小仇

Parteeetal在1990年给出了英语不是正则语言的证明。这个证明是基于带有中心-嵌套结
构(ccnterembedded structure)的一类着名的句子;这里是这种句子的一个变体:
   The cat likes tuna fish.
   The cat the dog chased likes tuna fish.
   The cal the dog the rat bit chased likes tuna fish.
   The cat the dog the rat the elephant admired bit chased likes tuna fish.
   与上面的那种either/or句子相比较,当这种句子变得更复杂时,理解起来也就更困难不过,
现在让我们假定,英语语法允许无限数目的嵌套。这样,为了证明英语不是正则语言,就需要证明
这类句子是与某种非正则语言同态的。在这些句子中,因为每个在前面的NP都必须与一个动词相
联系,这些句子的形式可以表示为:

   (the + noun)^n (transitive verb)^(n-1) likes tuna fish.
   要进行这种证明的基本思想是:证明这种句子的结构可以通过把英语与一个正剤表达式相交
而产生,然后使用抽吸引理证明,这样形成的句子不是正则表达式。
   为了建立一个简单的正则表达式,以便把它与英语相交从而产生这样的句子,我们来给名词组
(A)和动词(B)定义如下的正则表达式:
   A = {the cat, (he dog, /he rat. the elephant, the kangaroo... }
   B = {chased, bit, admired, ate, befriended,...}

   现在,如果取正则表达式/A^* B^* likes tuna fish/,并且把它与英语(把英语看成符号串的集合)
相交.结果形成如下的语言:
L =  (x^n)*(y^(n-1)) likes tuna fish, x ∈ A,y ∈ B
   通过抽吸引理.我们可以证明语言L不是正则语言。因为英语与正则语言的交不是正则语言,
所以英语不是正则语言(这是由于正则语言在交运算A是封闭的)。

tcxu
tcxu
你所引用的文章作者,是否应写成 Partee et al.,1990, 即 Partee 等人,文献 "Partee,B.H.,A.terMeulenandR.Wall.1990. MathematicalMethodsinLinguistics .Dordrecht:Kluwer."?
韦小仇
韦小仇
更正错别字 : ccnterembedded -> centerembedded
0
tcxu
tcxu

楼主的命题很有意思。楼上 韦小仇 的发言,也有道理。学习了一点背景知识,特将笔记出示如下。

为 韦小仇 添加注释 (出自: 冯志伟 "句子深度假说" ):

带有中心-嵌套结构(centerembedded structure)的一类著名的句子:

逐层定语嵌套结构的英语句子:
(1)      The cat likes tuna fish.(这只猫喜欢金枪鱼)
(2)      The cat the dog chased likes tuna fish.(狗追赶的这只猫喜欢金枪鱼)
(3)      The cat the dog the rat bit chased likes tuna fish.(老鼠咬的狗追赶的这只猫喜欢金枪鱼)
(4)      The cat the dog the rat the elephant admired bit chased likes tuna fish.(大象羡慕的老鼠咬的狗追赶的这只猫喜欢金枪鱼)

与讨论有关的参考:

  1. 师越,师海忠:自然语言是正则语言
  2. 正则语言的可递归性
  3. 《立委随笔:自然语言是递归的么?》

文献 3 指出:"...由于语用学的制约,人类实际的语言现象,表达中间recursion的括号数量是很有限的(很少超过三层,形象地说,只要大中小三种括号就够用了),...."。

 

 

返回顶部
顶部