正则语言中的密度问题

理论计算机科学电子笔记140（2005）67-79www.elsevier.com/locate/entcs正则语言Jakub Kozik1雅盖隆大学计算机科学研究所。Nawojki11，30-072Krako′w，Polandd摘要我们将给定语言S在给定语言L中的密度定义为从L中随机均匀选择长度为n的单词属于S的渐近概率。有些语言的密度是不存在的。我们证明了一个检查一个正则语言是否在另一个正则语言中具有密度的问题是可判定的。关键词：渐近估计，概率密度，正则语言1引言众所周知，不可能在有限字母表上的一组单词上定义均匀分布的概率测度。相反，我们可以考虑给定语言L在有限字母表上的密度为卡（Ln）d（L）= limn→∞、卡（）其表示随机且一致地选择的长度为n的字属于L的渐近概率。一个简单的例子，一个没有密度y是（（a+b）2） π（关于α b∈π={a，b}）。 只要密度存在且d（ω）= 1，就很容易发现密度总是非负的。此外，如果不相交语言L1，L2具有密度，则d（L1<$L2）=d（L1）+d（L2）.密度在不交集上是不可数可加的。[1]和[4]中使用形式幂级数研究了上述密度的概念另一种方法，基于马尔可夫链理论，在[2]中提出第1email:jkozik@ii.uj.edu.pl1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.06.02368J. Kozik/Electronic Notes in Theoretical Computer Science 140（2005）6722Σ卡（卡）给定两种语言SL，使得L包含几乎所有长度的单词，我们将语言S在语言L中的（条件）密度定义为d（S|L）= lim 卡（新加坡）n.n→∞卡（L卡）本文研究正则语言的条件密度。例1.1让我们将正整数表示为二进制字母表{1， 0}上的单词。那么所有正数的语言将是L= 1（1 + 0），偶数的语言将是S= 1（1 + 0）0。S在L中的条件密度给出了所有奇数的密度。数字，这是1，正如人们所期望的。在上面的例子中，语言L在完整语言中具有正密度。例1.2如果L=（a+bb）<$且S=a（a+bb）<$，则我们得到d（L）= 0且d（S|L）=105−1。在我们的论文中，我们专注于确定的问题，对于给定的正则语言SL，使得L包含几乎所有长度的单词，是否存在S在L中的密度，以及-在正的情况下-它是否是正的。S语言不是必不可少的，因为正则语言在交集下是封闭的。2初步定义设ε是一个有限的固定字母表，ε表示空单词。对于任何语言L，设L（n）表示长度为n的来自L的词的数目。我们会说，语言S在更大的语言中具有（正）密度LSwhenever the limnS（n）存在（且为正）。我们会考虑→∞L（n）这两种语言都是正常的。定义2.1复分析函数l（x）是一个基因决定函数，当l（x）=∞n=0L（n）·x n，对于任何x，该级数收敛。 的收敛半径∞n=0L（n）·xn由yλL表示。让我们注意到λ L≥1，因为L。定义2.2确定性有限自动机（DFA）是一个元组（Q，E，i，T），其中Q是状态的有限集合 E：Q×E→Q是一个转移函数（可以J. Kozik/Electronic Notes in Theoretical Computer Science 140（2005）6769可以被认为是一组标记的边缘），i ∈ Q是一个独特的初始状态和T ∈ Q是一组终端状态。函数E可以以明确的方式扩展为以下函数：Q×N，使得E（q，x·ω）=E（E（q，x），ω），其中q∈Q，x∈N，ω∈ NE（q，ε）= q，其中q∈ Q.DFAA（记为L（A））接受（识别）的语言是一个集合所有的词ω使得E（i，ω）∈T。换句话说，它是由图（Q，E）中从i到T的所有路径确定的定义2.3语言L是正则的当且仅当存在DFAA，使得L= L（A）。我们计算条件密度的方法是基于生成函数的。生成函数理论的介绍可以在[6]中找到。我们考虑的所有函数都是一个复变量的复函数。一个函数是有理的，如果它是一个商的多项式与整系数。下面的命题是众所周知的（见[4]，[3]）。命题2.4正则语言的生成函数是有理的。让我们注意到，有理函数的极点是其分母的根（我们总是假设有理函数的分母与其分子没有共同的根）。一个极点有重数k，如果它是分母的重数k很容易发现，对于每一种语言L，ns∞n=0L（n）·x的值等于其（有理）生成函数。并不是每个有理函数都是某个正则语言的生成函数。我们将根据[4]引用此类函数的特征，该特征基于其极点的局部化定义2.5有理函数有一个控制根，如果它是一个多项式，或者如果它有一个严格小于任何其他极点的模的实极点。定义2.6对于正整数k，有理函数有k-控制根，如果有重数为k的实极点，并且任何其他极点有严格较大的模或相等的模但严格较小的重数。Soittola定理（见[4]）描述了有理函数，这些有理函数是正则语言的生成函数。定理2.7（Soittola）有理函数f是生成函数，70J. Kozik/Electronic Notes in Theoretical Computer Science 140（2005）672q（x）22222某些正则语言当且仅当下列情况之一成立：(i) f有一个支配根(ii) 存在一个整数ν> 1和有理函数f0，.，fν−1有支配根，使得Σν−1f（x）=xi·fi（x ν）.i=0时在下面的章节中，我们测量正则语言L中正则语言S的密度。在不失一般性的情况下，我们假设SL。3语言的密度在本节中，我们假设集合有两个元素。 让我们从一个简单的例子，当更大的语言是“”。其母函数为1它的极点正好是1：1设S是正则的且s（x）=ps（x）S1−2x是的母函数S.设λS（长度分布级数的收敛半径Σ（S）严格大于1。这意味着该系列∞n=0S（n）2N收敛我们将获得Limn→∞S（n）2n= 0。假设λS=1。函数s（x）在半径为1的圆上不能有重数大于1的极点，因为这意味着对于足够大的n，S（n）>2n（参见第5节）。我们考虑两种情况。首先，假设s（x）有一个重数为1的极点。 因此s（x）分解如下：s（x）=Qs+p<$s（x），1− 2x q's（x）当rep？s（x）在d|X| ≤1。我不能暗示那帽子q's（x）2S（n）=Qs 2n+o（2n）语言S的密度等于Qs。让我们注意到，Qs也可以通过计算Limx→1s（x）11−2x1=s<$（），2其中res是通过从以下等式中消除因子1−2x得到的：J. Kozik/Electronic Notes in Theoretical Computer Science 140（2005）6771S.72J. Kozik/Electronic Notes in Theoretical Computer Science 140（2005）672νS在第二种情况下，s（x）在半径上有许多重数为1的极点，为1. 我们将证明S（n）分歧。 Soittolla2 2Ns0，..，s ν−1有控制根，且Σν−1（一）s（x）=i=0时s i（x v）·x i.为了解决矛盾，我们假设S有密度。然后(2)S（n）= QS2n+ o（2n）.因此，对于每个i = 0，..，v-1我们有（三）LimSi（k）=Q。k→∞2k·v+i我们可以推导出每个si（y）分解为QIs（y）=+r（y），i1 −2ν·yi其中ri（y）有界，y≤1没有支配根）。然后（如果ri（y）不是有界的，则si（y）将从（2）中，我们得到，S（k·v+i）=Qi·2k·v+o（2k·v+i）Qi=QS·2i.QS·2isi（y）=1 −2ν·y+ri（y）代入（1），我们得到Σν−1Σν−1Q ·2is（x）=si（xν）·xi=i=0时i=0时2016年01月01日01：03：03（S1 −（2x）ν+ri（xν））v−1（2x）i=QSi=0+1J. Kozik/Electronic Notes in Theoretical Computer Science 140（2005）677322−（2x）ν Σν−1i=0时xi·ri（xν）其中r（xQS=+r（x），1− 2xz−1x i·r（x z）有界，|X| ≤1。 这表明s（x）i=0i2在半径1上至多有一个极点，矛盾我们可以将上述观察总结为以下命题：命题3.1如果s（x）是某个正则语言的生成函数S在一个二进制字母表上，则以下之一为真：(i) s（x）在半径1上没有极点S的密度为0;74J. Kozik/Electronic Notes in Theoretical Computer Science 140（2005）67222q's（x）2(ii) s（x）在1中有一个极点，在半径为的闭圆盘中没有其他极点。1且S具有等于limx1s（x）·（1 −2x）;2(iii) s（x）在半径1上有多个极点而S没有密度。让我们注意到，上面的命题解决了一个问题，即如果更大的语言在完整的语言中具有正密度，则找到条件密度。4语言L有一个支配根让我们假设更大的语言L有一个支配根。通常，设λL表示L的长度分布的级数的收敛半径。这个例子与第三节中的例子非常相似。命题4.1设L是正则语言，l（x）是L的母函数，其控制根为λ L。 设S是正则语言，s（x）是S的生成函数. 以下情况之一为真：(i) s（x）在半径λL上无极点，且S在L中的密度为0;(ii) s（x）在λL中有一个极点，在半径为λL的闭圆盘中没有其他极点S在L中的正密度等于limxs（x）→λl（x）(iii) s（x）在λL的半径上有不止一个极点，并且S在λ L中没有密度。L.证据 情形（i）和（iii）类似于命题3.1的情形（用λ L代替1）。在（ii）的情况下，s（x）分解为：s（x）=QS+p<$s（x），1−λ−L1xq<$s（x）当rep′s（x）被绑定为或|X| ≤λL。Analogouslyl（x）= QL+p<$l（x）。我们立即获得1−λ−L1xq<$l（x）S（n）= QS·λ n+ o（λ n）。L L最后L（n）= QL·λ n+ o（λ n）。因此L Ld（S|L）= QSQL→;J. Kozik/Electronic Notes in Theoretical Computer Science 140（2005）6775LLλλλLLSQ和S+p′s（x）−1p's（x）Lim s（x）= lim−11−λLxq's（x）= limQS+（1−λL x）·q<$（x） S=.x→λLl（x）x→λLL+p<$l（x）x→λLQ+（1−λ−1x）·p<$l（x）QL−11−λLxq<$l（x）LLq<$l（x）最后一个等式成立，因为p′l（x）和p′s（x）是有界的，或|X|<λL。 Qq<$l（x）q<$s（x）5语言L有k-控制根设L是一个正则语言，l（x）是一个（有理）生成函数，L.假设l（x）有一个k-控制根λL。我们知道λL是重数k的分母的根，因此l（x）=C（λL−x）kC·λ−k+r（x）=L+r（x），（1−λ−L1·x）kK其中elimx→λLr（x）·（λL-x）=0（即r（x）does不具有多重性极点k在半径λL上）。因此⎛ ⎞n+k−1（四）l（x）=（C·λ−k）·.n=0例⎝k−1n·xn·λ−n+r（x）ΣC· λ−knk−1n∞w（n）=L·xn+·xn+r（x），（k− 1）！nn=0Lnn=0L其中w（n）是严格小于k−1的多项式。 因此nk−1（五）其中QL=C·−k（k−1）！L（n）=QL+o（λ−n·nk−1），L命题5.1修正任意正则语言S L。 如果L的生成函数有一个k-支配根，则下列之一成立：(i) s（x）的收敛半径严格大于l（x）的收敛半径，且S在L中的密度为0;(ii) 两个半径相等，但s（x）在半径λL上没有重数为k的极点，并且S在L中的密度为0。(iii) 两个半径相等，S有k-控制根，S在L中有正密度;λn.76J. Kozik/Electronic Notes in Theoretical Computer Science 140（2005）67L（n）(iv) s在半径λL上有许多重数为k的极点，而S没有密度（即序列S（n））发散）。J. Kozik/Electronic Notes in Theoretical Computer Science 140（2005）6777λLλLL（n）ęL（n）λLLLLLnL证据情形（i）类似于命题4.1中的情形（i）。在情形ii中，当s（x）在重数k的半径λL上没有极点时，我们k−2可以确定SJ满足SJ（n）≥S（n）（对于所有n）且SJ（n）=QSJnnL+o（λ−n·nk−2）。 因此L在S中的密度为0。让我们考虑情况（iii），当s有重数k的控制根它等于L类似于（5），我们有nk−1S（n）=QS+o（λ−n·nk−1）L因此序列S（n）请注意，L在情形（iv）中，当s在半径λ上有许多重数k的根时，我们将显示序列S（n）发散。让我们假设，作为一个矛盾，存在QS使得（六）LimS（n）=Q S。这意味着n→∞L（n）QLnk−1k1n（七）S（n）=QS·n +o（n−·λ−L）。L根据Soittola定理（2.7），存在函数s0，...，s ν−1，使得Σν−1s（x）=si（xν）·xii=0时并且每个si（x）在其收敛半径上恰好有一个极点 如果一些函数si（x）在λν中没有极点，这意味着S（n）发散LL（n）（因为至少有一个在λν中有极点）。 如果所有半径都大于λν，则L L函数s（x）在λL中没有极点。让我们假设所有的半径都等于λν。 因此，类比地（4）我们得到s（xν）=Si +r（xν）i（λν−xν）kiSI=（k−1）！·λν·kΣ∞（n=0例nk−1λn·ν·xn·v+ Σ∞n=0例wi（n）λn·ν·xn·v） +ri（xv），其中wi是严格小于k−1的多项式，Si是非负实数。然后i νSi.nk−1n ν+in（n）Σn ν+i ν i78J. Kozik/Electronic Notes in Theoretical Computer Science 140（2005）67LLx·si（x）=（k−1）！·λν·kn=0例λn·ν ·x·+n=0例λn·ν·x·+ri（x）·xJ. Kozik/Electronic Notes in Theoretical Computer Science 140（2005）6779LLLLLLLLLLSLSi· λi.n（vn）k−1Σn（n）=L·xn·v+i+·xn·v+i+ri（xν）·xi（k−1）！·λν·k·νk−1n=0例λn·v+in=0例λn·v+i对于某个多项式w i（n）= w i（n）·ν k−1。因此，因为对于某个多项式v i，（v·n）k−1=（v·n +i）k−1− v i（n），使得deg（v i）y（（q（y）= 0 <$|y| ≤ |X|（x = x））。f =0。82J. Kozik/Electronic Notes in Theoretical Computer Science 140（2005）67q（x）nS（n）211122111111定理2.7保证这样的x是一个实数。上面的公式对于多项式q是否为真的问题可以通过塔斯基定理来判定（我们可以将上面的公式转化为实数上的等价公式）。类似地，对于函数f（x）=p（x），拥有一个domi的属性-重数d的根可以用公式表示x [q（x）= 0 <$qJ（x）= 0 <$. q（d）/= 0∧∀y ((q (x)= 0 ∧ qJ (x)= 0 ∧.. q（d）= 0 |y| ≤ |X|（y = x）]。由于控制根的重数是由多项式q（x）的次数限制的，所以任何重数的控制根的性质都是可判定的，并且在正的情况下，有可能找到那个重数。让我们注意到，对于两个具有相同重数的支配根的函数，可以写出一个比较这些根的公式使用上面概述的方法，我们可以区分命题3.1、4.1、5.1中的所有情况和第6节中的情况（i）和（ii）。在第6节的剩余情况（iii）中，我们必须比较部分极限以确定语言S在L中是否有密度。我们提出了一个比较部分极限的过程来回答这个问题。给定两对具有控制根（l1，s1），（l2，s2）的有理函数我们必须检查limL1（n）n→∞S1（n）L2（n）. 如果没有基因缺失，→∞我们可以假设两个极限都不是0。设l1（x）=ps（x）pl（x）ql（x）（λ1−x）k1（分别为s（x）=1），使得k是支配的重数1qs（x）（λ1−x）k11求l1的根λ1。让我们注意到，L1（n）l1（x）ps（λ1）·ql（λ1）Limn→∞S1（n）= limx→λ1s1（x）=1 1pl（λ1）·qs（λ1）函数g（x）=ps（x）·ql（x）可以通过消除COM来计算。1pl（x）·qs（x）从s1（x）的分母和分母中提取的分数。Letl（x）=pl（x）ps（x）l1（x）22ql（x）（λ2−x）k2（分别）g1（x）=2）。类似地，我们计算比率-qs（x）（λ2−x）k2nal函数g2（x）对于（l2，s2）. 我们可以定义一个偏密度如：<$λ1<$λ2：[λ1是l1<$λ的多重性k1的一个指定的r00λ2是l2∞的重数k2=limJ. Kozik/Electronic Notes in Theoretical Computer Science 140（2005）6783g1（λ1）= g2（λ2）]。所以所有偏密度的相等性也是可判定的84J. Kozik/Electronic Notes in Theoretical Computer Science 140（2005）6702因此，我们可以区分第4-6节中描述的所有分类情况，定理7.2给定两个正则语言S<$L， S在L中具有密度，且在正情况下密度是否为0。7.1复杂性我们假设语言是由DFA给出的。上面概述的过程可以很容易地改进为具有在实数的有序域中验证一阶公式的有效性的复杂性针对该问题的最知名算法在双指数时间内工作。然而，使用更简单的方法（如Sturm级数），我们可以在多项式时间内解决简单的情况（即除了L在收敛半径上有许多极大重数的极点之外的所有情况）。8平衡密度在上面的定义中，我们使用长度来衡量单词的复杂性。我们可以通过给每个字母加上权重来概括它。设k ={a，b}，Qa和Qb表示字母的权重。对于每个词ω∈ π πlet |ω|x表示字母x在ω中出现的次数。我们定义了一个平衡的复杂性关于ωasc（ω）= Q a·|ω|a+ Q b·|ω|B.我们定义了一个平衡密度的L-半乳糖苷酶Card（L<$c−<$1（n））d（L）= lim.n→∞Card（c−1（n））合理的做法是为字母选择权重，使它们没有公约数，以避免无限多的0类分数。为了说明平衡密度可以不等同于密度，让我们考虑语言（（a+b）2）n，其中没有密度y，但是当我们将以下权重分配给字母Qa=1，Qb= 2时，它具有平衡密度1。判定正则语言S在正则语言L中是否具有（正）平衡密度的问题并不比判定密度的问题难。我们可以通过替换每个出现来构造语言SJ和LJ在语言中，每个字母x都有xxyxx（语言SJ和LJ都是正则的）。然后我们有：d（S|L）= d（S）|LJ）。J. Kozik/Electronic Notes in Theoretical Computer Science 140（2005）67859结论我们证明了一个正则语言是否在另一个正则语言中具有（正）密度的问题是可判定的，并且可以在双指数时间内解决，只要语言由确定性有限自动机给出。这种计算复杂性是由实数有序域中的量子消除的一般过程的复杂性决定的。另一方面，本文提出的算法所产生的公式是特殊类型的，似乎可以获得更好的复杂度界限。然而，我们预计，在一般情况下，这个问题不能在多项式时间内解决在进一步的工作中，我们希望集中在密度的明确上下文无关的语言，生成函数是代数。引用[1] Berstel J.，Sur la densite de langages formels，ICALP，1972，345-358.[2] BodirskyM. ， and d GüartnerT. ， andd vonOertzenT.和 SchwinghammerJ. ，EuccientlyComputing the Density of Regular Languages ， Proceedings of Latin AmericanInformatics（LATIN[3] Flajolet P.， 和R.Sedgewick，http://algo.inria.fr/flajolet/Publications/AnaCombi1to9.pdf网站。[4] Salomaa A.，和M.苏文，[5] 塔斯基·A 初等代数和几何的判定方法，第2版，加州大学。Press，Berkeley，1951.[6] 威尔夫·H《生成功能学》第二版北京：人民出版社，1993.