没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记53(2002)网址:http://www.elsevie r. n l/l oc ate/en tcs/vol e53. ht ml 9页Poly-Slender和Parikh Slender上下文无关语言的Chomsky-SchützenbergerT型伊藤雅美2理学院数学系京都产业大学京都603,日本Carlos Mart' in-Vide3数学语言学研究小组P Ca。ImperialTa`raco1,43005Taragona,西班牙Victor Mitrana4布加勒斯特大学数学系Str. Academiei 14,70109,布加勒斯特,罗马尼亚摘要本文提出了k-多细长上下文无关语言的Chomsky-Schützenbrgerger类型特征,作为Dyck语言和(2k+1)-多细长正则语言的交的同态象.给出了一个更强的结果,即当考虑所有多细长上下文无关语言族时,同态和Dyck语言都是确定的,而与给定的多细长上下文无关语言无关. Parikh细长上下文无关语言也得到了类似的特征。1由科学研究补助金支持的工作。10440034,日本科学促进会和通用电气公司,SB97 -001105082 电子邮件地址:ito@ksuvx0.kyoto-su.ac.jp3 电子邮件地址:cmv@astor.urv.es4 电子邮件地址:mitrana@funinf.cs.unibuc.roc2002年由Elsevier Science B出版诉 在CC BY-NC-ND许可下开放访问。伊藤、马特·恩维德和米特21介绍长期以来,关于语言中词的长度的考虑一直是许多研究者感兴趣的焦点。因此,在[5](也见[3,14])中,对于给定的语言L,人们与每个非负整数n相关联,L(n)中的n个非负整数的n个整数都是最多的n,记为d#L(n)。然后定义L的fL( z)=X#L( n) znn>0并证明了这个函数是比域上的代数函数,只要L是一个明确的上下文无关语言.此外,生成函数的超越性是[7]研究上下文无关语言内在歧义的主要工具。此外,在Lindenmayer系统中涉及单词长度考虑的深入结果已经在一系列论文中报道[6,9,15,20]。受密码学中出现的一些问题的启发,[1]引入了细长语言,这些语言最多包含恒定数量的任何长度的单词。 粗略地说,[1]中考虑了Richelieu密码系统的以下形式语言方法:使用长度为n的加密密钥加密明文,产生与加密密钥相同长度的密文。如果合法接收者知道密钥,那么它可以很容易地恢复原始文本。将所有可能的密钥传输到合法接收方时出现问题为了降低恢复的复杂度,密钥应该来自一种简洁的语言,使得接收者可以为每个密文测试有限数量的密钥。有兴趣的读者可以参考[1]。在[18,21]和[11]中分别报道了细长正则语言和上下文无关语言的特征许多不同类型的细长语言的许多方面已经在一系列论文中进行了研究[16,17]。Raz在[19]中将slenaries的概念扩展到poly-slenaries,poly-slenaries语言是一种语言,其长度为n的单词的数量由n中的多项式的值为所有n0。文献[21]给出了多细长正则语言的特征化,而文献[12]给出了多细长上下文无关语言的特征化。本 文 提 出 了 一 个 k- 多 细 长 上 下 文 无 关 语 言 的 特 征 , 即 Cchomsky-Schutzenberg型[5],它是Dyck语言与(2k +1)-多细长正则语言的交集的同态象. 当去掉k时,给出了一个更强的结果,即同态和Dyck语言与给定的多细长上下文无关语言无关. 此外,相反的断言也是正确的。得到类似的特征,伊藤、马特·恩维德和米特312kKParikh slim context-free语言,即每个Parikh slimcontext-free语言都是Dyck语言与Parikh slim正则语言的交集的同态象,但反之则不成立。2基本定义和以前的结果字母表V上的所有单词的集合由V表示,而V += V在你写的那首歌里。对于每个hwordx2V+,其中heelegh由jx j表示,jx ja提供字母a在x中出现的次数。V的任何子集都称为V上的语言。对于非负整数,语言L称V是k-有界的,如果存在单词x;x;:;x12k在V上,使得Lfxgfx g:fx g。L是有界的,如果它对某个k0是k-有界的.对于基本概念和结果的组合的话,读者是指[4,13]。给定一个语言L,映射#L(n)给出了L中所有长度为n的单词的个数。形式上,#L(n)=card(fx2Ljxj =ng):对于非负整数k,语言L称为k-多细长语言,如果#L(n)2 O(nk):此外,L是多细长语言,如果它是k-多细长语言,对于某个k0。任何0-poly-slim语言也称为slim。结果见[19]。定理2.1多细长上下文无关语言类恰是有界上下文无关语言类。此外,[19]中命题1的证明的一个直接结果在续集中是有用的,命题2.2 k-有界语言是(k-1)-poly-slim,对任意k 1。对于V=f aja 2 Vg,V w e d e n t e nalphabtVweden t e ne 语言转换(V [V])由具有规则集fS! SS;S! “g [fS! A Saj a2VgiscalledledheDycklanguageeoverVd enotdDV.Wewriew=a1a2 :anforw=a1a2:an,ai2V,1in.现在我们回顾一下Dyck循环的定义[12]。设Vk=fa1;a2; :;akg且z=z1z2:z2k2DVk 与zj2Vk[Vk,1j2k,jzjai]成一个字 =jzj ai =1for all1ik,并且U是一个独立的函数,Vk[Vk. 对于同态h:(U [V] k[V)! U和一些整数Kni0、1个ik,我们定义同态hn1;n2;:::;nk通过:(U[Vk[五 ) ! Uhn1;n2;:;nk(a) =aforalla2U;h(a) =uni;1ikn1;n2;:;nki iih(a) =vni;1ik;n1;n2;:;nki ii伊藤、马特·恩维德和米特4对于一些u ;v2U,1我K.然后对于某些单词w;w ;::;w2U我我语言01 2kD=fhn1;n2;:::;nk(w0z1w1z2w2: : :z2kwk)jni0;1ik g叫做k-戴克环显然,相同的集合D可以通过改变同态h1;1;:;1或Dyck字z来获得。 我们说z是D的一个底层字,h=h1;1;:;1是D的一个底层同态.根据上述记号,[11]和[12]的主要结果可以写成:定理2.3上下文无关语言是k-多-细长的当且仅当它是(k+1)-Dyck循环的有限并。3多细长上下文无关语言我们说,如果对于任何语言,语言类L1在Chomsky-Schuützenberrgery类型中是弱特征的,则语言类L2是弱特征的在字母V上,存在字母U,语言L22L2和从U到V的同态h,其中L1=h(DU\L2).进一步,如果h(DU\L2)2L1对U上的任意语言L22L2和从U到字母表V的任意同态h成立,则我们说语言类L1与语言类L2在Chomsky-Schützenberg型上具有强特征.这样一个强有力的特征在形式语言理论[5]中是最受关注的语言家族定理3.1上下文无关语言族在Chomsky-Sc hützenberger型中被强刻画为规则语言族。现在我们准备证明本节的主要结果定理3.2对任意k0,k-多细长上下文无关语言族与(2k+1)-多细长正则语言族是弱Chomsky-Sc hützenberger型的.证据 设V是一个给定的字母表,L是V上的k-多细长上下文无关语言. 根据定理2.3,L可以被写为(k+1)-Dyck环。让我们用D1;D2;::;Dm来表示这些(k+1)-Dyck环对于一些M1。此外,假设D=fh(Di)(w(Di)z(Di)w(Di)z(Di)w(Di):z(Di)w(Di))in1;n2;:;nk+1011 222k+22k+2j n j0; 1Jk+ 1g;ww(Di);w(Di); : : :;w(Di)2V对于任何一个人来说,0 12k +2V(Di)[V(Di)=fz(Di);z(Di); : :z(Di)g;k+111 2 3 4 5 6 7 8 9 9102k+2伊藤、马特·恩维德和米特5k+1(五)。J对于所有的11M。此外,所有字母V(Di)可以相互假设不相交我们认为字母表M mU=[V(Di)[[fc(i);c(i); : :;c(i) g;i=1k+101i=12k+2(i)m( Di)wherecj ,1im;0j2k+2,则在Si= 1(Vk+1)中不存在一个新的整数 的(Di)k+1现在我们定义正则语言MR=[fc(i)c(i)gfz(Di)gfc(i)c(i)gfz(Di)gfc(i)c(i)g:fz(Di) gfc(i)c㈠g;0 01i=11 1 2 222k+22k+2 2k+2和同态g:(U [U]) ! V定义为g(c(i)) =w(Di);J J(i) =“;g(z(Di))=h(Di)(z(Di));j1;1;:;1j对于所有1我m和1J2k+ 2。显然,对于每1下面的关系成立:D=g(D\fc(i)c(i)gfz(Di)gfc(i)c(i)gfz(Di)gfc(i)c(i)g:iU0 0 1 1 1 2 2fz(Di)gfc(i)c(i)g):2k +22k+2 2k+2因此,L = g(D U\R)也成立。 由命题2.2可以得出上面的正则语言R是(2k +1)-poly-slim,这包括了证明。2由于每个k-Dyck循环的同态像都是k-Dyck循环,因此所有的k-poly-slim上下文无关语言族k 0在同态下是封闭的。我们不知道上述刻画中的(2k+1)-poly-slim正则语言族是否可以用k-poly-slim正则语言族来代替 这将意味着一个强有力的表征类的k-聚细长上下文无关的语言为每个k0。另一个相关的问题是关于最小的m值k,使得每一类k-多细长语言都能在Chomsky-Schützenberg型中与m-多细长正则语言族弱特征化。我们猜想这个最小值正好是2k+ 1,所以前面的结果在这方面是最优的几个可判定性问题,这仍然是开放的,在本文中,自然,如果我们的猜想是错误的,就会出现1. 给定一个k-poly-slim语言,上面的m的最小值是可计算的吗?伊藤、马特·恩维德和米特6n0的2. 是否存在k-poly-slim语言,它们不是(k1)-poly-slim,使得上述最小值是k?在肯定式中,我们能否决定一个给定的k-poly-slim语言是否具有这个性质,即它是否允许一个具有k-poly-slim正则语言的Chomsky-Schuétzenbergercharacterization但显然定理3.3多细长上下文无关语言类是多细长正则语言类的强特征。在Chomsky-Schütze两种类型的特征化中,正则语言和Dyck语言的字母表以及同态都依赖于给定的多细长上下文无关语言. 该结果还可以改进,使得可以确定所有上述对象,而不管给定的多细长上下文无关语言。 这种改进是基于[8]通过定理2.1对多细长上下文无关语言的相同特征化。一个语言族L在对偶环下是闭的,如果对任何语言L2Landanytwordsx;y,thelanguageSfxngLfyng在L中。定理3.4多细长上下文无关语言族是包含所有单例语言的最小族,并且在以下操作下是封闭的:(i) 工会,(ii) 连接,(iii) 成对回路我们把获得一个多细长上下文无关语言所需的上述操作的最小数目称为L的阶数。现在我们声明定理3.5设V是一个字母表,可以确定一个新的字母表U和从U到V的同态h,使得对于V上的每个多细长上下文无关语言L,存在一个多细 长 正 则 语 言 R 关 于 U , 使 得 h 在 L=h ( DU\R ) . 更 进一步, h(DU\R)是一个p-slen-de-r上下文无关的p-slen-de-r,对于任意的从U到V的同态h和任意的p-slim正则语言R.证据 对于给定的字母表V,我们构造字母表W= V [f#g[V0],其中V0=fa0ja2Vg,并且d#是一个新的对称。对于w=a1a2: an,ai2 V,1在n中,我们用w 0表示单词a 0a 0:a 0。把U=W[W.同态h定义为:12Nh(a)=h(a0)=a;a2V;andh(a)=“;a2Un(V[V0]):设L是V上的多细长上下文无关语言。我们用L阶的归纳法证明了这个状态,比如说k。如果k= 0,则L是单例伊藤、马特·恩维德和米特7U11lang uag e,L=fxg. 把这个简单的表达式转化为规则语言R=fxxRg,其中xR提供了x的镜像。显然,L = h(D\R)。设L1,L2是V上两个阶数小于k的多细长上下文无关语言. 根据归纳假说,Li=h(DU\Ri); i=1;2:如果L=L1[L2,nL=h(DU\(R1\R2),则R是任意的. 如果L=L1L2,则L=h(DU\(R1f#gR2f#g))holds.如果L=S我0 fxigLfyig,其中L=h(D \(fx y0Rg Rfy0xRg))holds.因此,定理的第一部分得到了证明。第二部分是明显24Parikh Slender语言而不是长度为n的单词,在[10]中,人们计算具有相同Parikh向量的单词的数量特别地,对Autebert,Flajolet,和Gabarro [2]关于有限词的coprefix语言的固有歧义性的结果,得到了一个非常好的简单的证明根据定义,如果V=fa1;a2; :;amg是一个字母,并且w2V是一个单词,则Parikh向量V(w)定义为:V(w)=(jw ja1;jw ja2; :;jw jam):一个语言LV被称为Parikh细长,如果存在正整数k,使得对于每个正整数向量(i1; i2;:;im),L中最多有k个单词具有Parikh向量(i1; i2;:;im)。一个很自然的问题是Parikh slim上下文无关语言家族是否具有Chomsky-Schuützenbergertypecharterizationn。正如我们所看到的,在前一节中,这个问题对于细长语言是开放语 言 LV 被 称 为 多 循 环 语 言 , 如 果 存 在 k1 和 字 符 串 u1; v1; u2;v2;:;uk;vk;uk+12V,使得满足以下两个条件(i) L= u1 v u2 v:uk vuk+112k(ii) V(v1);V(v2);V(vk)相对于Q线性地扩展:Parikh细长正则语言的以下特征出现在[10]中。定理4.1正则语言是Parikh slim当且仅当它是不相交的多个循环语言的有限联合。很容易注意到,每个Parikh slim上下文无关语言都是poly-slim的,并且根据定理4.1,定理3.2证明的正则语言是Parikh slim的。所以我们U伊藤、马特·恩维德和米特8VJustgotaChomsky-SchuützenbergeecharacterizationnofParikhslen-dercontext-free languages.定理4.2 Parikh细长型上下文无关语言族是Parikh细长型正则语言族的弱特征。然而,Parikh细长语言族不能用Parikh细长正则语言族来强刻画,如下面的例子所示。 我们把DV语言定义为V=fa;b;cg,把P语言定义为R=a+a+b+c++,把同态mh(V[V])定义为a;bg定义为dbyh(a)=h(c)=a,h(b)=b,和dh(x)=“,x2V。我们有一个h(D\R)=a+b+a+这不是一种帕里克语引用[1] 而 且 , M. ,J.好 的, 好 的 。 Paunn , anddA. 李 晓 云 , 李 晓 云 .Sci. 116(1993),339[2] Autebert,J. M.,P. Flajolet和J. Gabarro,无限词和模糊上下文无关语言的前缀,Inform。过程Letters25(1987),211- 216.[3] Berstel,J. 我想我们应该有一个简单的语言形式。 在M。我也是,编辑,“Automata,Languages and Programming”North-Holland,1972,345- 358.[4] Choffrut,C. ,dJ. Karhumáki,Combinatoricsonwo rds。 InG. Rozenberg和A.Salomaa,eds. I,Springer-Verlag,Berlin,1997,329-437.[5] Chomsky,N. ,nd M.P.Schützenberger,Thealgebra aictheo ryoffixedxt-freelanguages. 在p.Bradford和D.Hirschberg,eds.“ComputerProgrammingandFormalSystems”,North-Holland,Amsterdam,1963,118-161.[6] 去死吧,杰, Gh. Paunn,anddA. Salomaa,OnthinnessanddslaughternessofLlanguages,EATCS Bulletin49(1993),152[7] Flajolet , P. , 分 析 模 型 和 上 下 文 无 关 语 言 的 歧 义 , 理 论 。 Sci. 49(1987),283[8] Ginsburg,S. “The Mathematical Theory of Context-Free Languages”,McGraw-Hill,[9] Honkala , J. , Decision problems concerning thiness and sleneficiary offormal languages,Acta Inform。35(1998),625伊藤、马特·恩维德和米特9[10] Honkala,J.关于Parikh细长语言和幂级数,J.Comput. 系统科学52(1996),185[11] 伊利湖关于细长上下文无关语言的一个定理。Comput. Sci. 132(1994),427[12] 伊利湖,G. Rozenberg和A. Salomaa,A characterization of poly-slimcontext-free languages.告知。Appl. 34(2000),77[13] Lothaire,M.“Combinatorics on Words”,Addison-Wesley,Reading,MA,1983.[14] Maurer,H.A.,和M. Nivat,有理集的有理双射,Acta Inform。13(1980),365[15] 西田,T.,和A.Salomaa,Slender 0L语言,Theoret.Comput. Sci. 158(1996),161[16] 帕帕温,Gh。,ndA. Salomaa,DecisionproblemsconcerningthethinnessofD0L languages,EATCSBulletin46(1992),171[17] 帕帕温,Gh。,ndA. Salomaa,与其他语言密切相关,Comput. Sci. 120(1993),293[18] 帕帕温,Gh。,ndA. Salomaa,Thinanddslimmerlanguages,DiscreAppl.MATH。61(1995),257[19] Raz,D. 上下文无关语言中的长度考虑,理论。Sci. 183(1997),21[20] 罗森伯格,G.,和A.Salomaa,“L系统的数学理论”,学术出版社,纽约,1980年。[21] Shallit,J.Numeration Systems,Linear Recurrent,and Regular Sets,Inform.的Comput。113(1994),331
下载后可阅读完整内容,剩余1页未读,立即下载
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 利用迪杰斯特拉算法的全国交通咨询系统设计与实现
- 全国交通咨询系统C++实现源码解析
- DFT与FFT应用:信号频谱分析实验
- MATLAB图论算法实现:最小费用最大流
- MATLAB常用命令完全指南
- 共创智慧灯杆数据运营公司——抢占5G市场
- 中山农情统计分析系统项目实施与管理策略
- XX省中小学智慧校园建设实施方案
- 中山农情统计分析系统项目实施方案
- MATLAB函数详解:从Text到Size的实用指南
- 考虑速度与加速度限制的工业机器人轨迹规划与实时补偿算法
- Matlab进行统计回归分析:从单因素到双因素方差分析
- 智慧灯杆数据运营公司策划书:抢占5G市场,打造智慧城市新载体
- Photoshop基础与色彩知识:信息时代的PS认证考试全攻略
- Photoshop技能测试:核心概念与操作
- Photoshop试题与答案详解
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)