正则运算的实态处理与Sakoda-Sipser问题

可在www.sciencedirect.com在线获取理论计算机科学电子笔记321（2016）23-39www.elsevier.com/locate/entcs正则运算的实态处理与Sakoda-Sipser问题J. Andres Montoya1，2 David Casas3Dep artamentodeMatem'aticasUniversidad Nacional de ColombiaBogot'a，Colombia摘要在这项工作中，我们研究了一些方面的状态复杂性相关的非常著名的Sakoda-Sipser问题。我们研究了正则运算的状态复杂性，我们调查了已知的事实，顺便说一下，我们对一些著名的结果给出了新的、更简单的证明。对艺术状态的分析使我们找到了一个新的有意义的概念：真实状态处理。我们研究这个概念，寻找一个模型的确定性有限自动机持有这样一个有趣的属性。我们建立了一些初步的结果，这似乎表明，不存在一个具有正则表达式实态处理的确定性有限自动机模型，但另一方面，我们能够展示一个确定性模型有限自动机具有无星正则表达式的真实状态处理关键词：有限自动机，状态复杂度，正则表达式，正则运算。1介绍众所周知，非确定性有限状态自动机（1NFAs）是强大的作为确定性有限状态自动机（1DFA），在这个意义上，1NFA只能识别正则语言。众所周知，1NFA比1DFA更强大，因为1NFA不能被1DFA模拟，而1DFA在状态数方面具有多项式开销。 Sakoda和Sipser [8]询问了1NFA是否可以通过状态数为多项式的双向确定性有限状态自动机（2DFA）来模拟。这是所谓的Sakoda-Sipser问题中包含的问题之一。Sakoda-Sipser问题是一个关于双向性如何、何时以及在何种程度上能够取代非决定论的问题。如果这样一个问题能有一个肯定的答案，那将是一个好消息事实上，鉴于1第一作者要感谢哥伦比亚国立大学和通过R.P. Hermes 16860提供的支持2电子邮件：jamontoyaa@unal.edu.co3电子邮件：dfcasast@unal.edu.cohttp://dx.doi.org/10.1016/j.entcs.2016.02.0031571-0661/© 2016作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。24J.A. 蒙托亚湾Casas/Electronic Notes in Theoretical Computer Science 321（2016）231NFA（和2NFA）是不可靠的自动机，不能在实践中使用。但是，尽管它们具有纯粹的理论价值，1NFA具有一些显着的特征，我们希望在某种可靠和可实现的有限状态自动机模型中具有这些特征。因此，我们认为Sakoda-Sipser问题是以下更一般问题的特例：如何，何时以及在何种程度上，具有附加能力的确定性有限状态自动机与非确定性对应物一样强大和有效？在讨论后一个问题之前，我们必须考虑以下问题：非确定性有限自动机的那些显著特征是我们如果有人被要求证明正则语言集在正则运算下是封闭的，如果允许使用1NFA，那么很容易得出这样的证明。如果在证明中不得不使用较弱的1DFA模型，事情就变得更难了此外，这样一个简单的证明使用1NFA产生一个线性时间算法，称为汤普森计算一个O（|α|）-状态1 NFA识别语言L（α）。我们说一个确定有限自动机模型具有Thompson性质，当且仅当存在一个多项式时间算法，它在输入α上计算一个O（|α|c）-模型中的状态自动机，它识别语言L（α），（其中c是某个固定常数）。因此，我们有汤普森性质对1NFA成立，而很容易证明它对1DFA不成立。我们认为Thompson性质是1NFA的一个值得注意的特征，因为它允许这些自动机高效地处理正则表达式。考虑到正则表达式的处理是分配给有限自动机的主要任务之一。不幸的是，1NFA的非确定性本质使它们成为上述问题的不可实现的解决方案。因此，如果我们能展示一个汤普森性质成立的自动机的确定性模型，在这项工作中，我们调查了以下问题：如何，何时以及在何种程度上有可能定义一个模型的确定性有限自动机的汤普森性质举行？注1.1我们将Sakoda-Sipser问题理解为这样一个问题：是否存在一个有限状态自动机的确定性模型，它可以有效地模拟非确定性自动机？很明显，对Sakoda-Sipser的肯定回答意味着我们的问题可以得到积极的解决。另一方面，如果我们能对我们的问题给出肯定的答案，我们就不能立即得出结论，认为Sakoda-Sipser也有一个肯定的答案。这是因为非确定性自动机比正则表达式更简洁[4]。注1.2我们假设读者知道有限状态自动机的基本模型的定义，如DFA，NFA，2DFA等。感兴趣的读者可以参考优秀的参考文献[9]。工作安排和贡献。这项工作被组织成J.A. 蒙托亚湾Casas/Electronic Notes in Theoretical Computer Science 321（2016）2325C六个部分。在第1节中，我们介绍了我们在本文中研究的问题，介绍了真实状态处理的概念。在第二节中，我们考虑了DFAs模型，并给出了一些著名结果的简单证明在第三节中，我们研究了2DFA，我们证明了这些自动机不具有正则操作的实态处理。此外，我们证明了一个严格的超多项式分离的模型1NFA。在第四节中，我们考虑了一个双向卵石自动机模型，并证明了它不能处理实状态的级联。在第五节中，我们介绍了一个新的多字节自动机模型，并证明了它具有无星正则表达式的实态处理在第6节中，我们提出了一些结论性意见。2非确定有限状态自动机与Thompson性质有限自动机的模型是接受正则语言的基于状态的识别设备（automata）的无限集合C，这意味着给定正则语言，必须存在C中的自动机识别该语言，并且给定M ∈C，M识别的语言是正则的。我们感兴趣的是有限自动机的标准模型，其成员由一组有限的内部状态、一个过渡函数以及其他（有限）资源组成。对于所有这些模型，下面的定义是有意义的。定义2.1我们说有限自动机的模型，比如C，解决了有效处理正则表达式的问题，当且仅当存在多项式时间算法T，它在输入α（其中α是正则表达式）上计算Mα∈ C，使得：• L（Mα）= L（α）。• |n= 0（|α|其中Q（M α）表示自动机M α的内部状态集，符号|α|表示α的长度，c是某个正常数。|denotes the length of α, and c is some positive constant.是否存在一种有限自动机模型来解决高效处理正则表达式的问题是的，至少有一个这样的模型，它是1NFA的模型。存在一个线性时间算法T，它在输入α上输出Mα，一个1NFA使得L（α）=L（Mα），并且使得|Q（Mα）|n =0（|α|）的。算法T被称为汤普森算法[ 10 ]，它是一个朴素的算法，利用正则表达式的递归定义加上以下关键事实：存在三个常数C U，C ·和C，使得给定两个1NFA，比如M和N，可以在线性时间内计算三个1NFA S，S ·和S，使得：(i) S接受语言L（M）<$L（N），其状态数等于n+m+C<$。(ii) S·接受语言L（M）·L（N），其状态数等于n+m+C·。(iii) S接受语言L（M），其状态数等于n+C。26J.A. 蒙托亚湾Casas/Electronic Notes in Theoretical Computer Science 321（2016）23很容易检查，上述三个事实保证输出 Thompson算法的自动机Mα满足条件|n= 0（|α|）.|). 也很容易检查较弱的条件（例如|Q（S）|≤ 2 n + m + C∞）不足以保证Thompson算法的存在性。 我们说汤普森性质对C成立，当且仅当，利用正则表达式的递归定义的朴素算法可以在状态约束下工作 |Q（Mα）|n=0（|α|（c）。 对于哪些型号的自动机汤普森的财产持有？我们不会描述这些模型，但是，首先，我们将展示一个条件，保证这个难以捉摸的属性实际上成立。定义2.2我们说C具有正则运算的实态处理4（实态转换）当且仅当存在三个常数CU，C·和C·，使得给定两个C-自动机，假设M和N，分别具有m和n个状态，人们可以在多项式时间内计算三个C-自动机S·，S·和S·，使得：(i) S接受语言L（M）<$L（N），其状态数等于m+n+C<$。(ii) S·接受语言L（M）·L（N），其状态数等于m+n+C·。(iii) S接受语言L（M），其状态数等于m+C.我们有命题2.3如果C有常规操作的实态处理，那么汤普森财产持有C从现在开始，我们将研究以下问题问题2.4（实态处理问题）是否存在一个有限自动机的确定性模型，它对常规操作进行实态处理？3确定性单向有限自动机我们将考虑的第一个确定性自动机模型是1DFA的标准模型。在这个模型中，我们使用了一个强大的工具来降低给定正则语言的状态复杂度，这就是Myhill-Nerode定理。定义3.1给定一个字母表，给定一个语言L，我们用以下方式定义一个等价关系RL×：给定x，y∈，我们有xRL y当且仅当对所有w∈，xw∈Lyw∈L。定理3.2（Myhill-Nerode）4与实时概念的类比J.A. 蒙托亚湾Casas/Electronic Notes in Theoretical Computer Science 321（2016）2327RLRLL语言是正则语言当且仅当商语言是有限的。此外，委员会认为，如果语言L是正则的，则识别L的最小1DFA具有|Σ∗ |states .”[19]见《明史》。我们可以使用Myhill-Nerode定理来降低该模型中联合的状态复杂度下一个结果是自动机理论民间传说的一部分，但下界的证明既不平凡，也不容易在标准参考文献中找到，为了完整起见，我们将其包括在内引理3.3（联合的上下界）(i) 设N是具有n个状态的1DFA，并且设M是具有m个状态的1DFA（在相 同的输入字母表），语言L（N）<$L（M）可以由具有至多nm个状态的1DFA识别。(ii) 存在一个正则语言序列，比如（Pn）n≥1，使得对于所有n≥ 1，语言Pn可以被具有n个状态的1DFA接受，但是对 于 无限多对（n，m），语言Pn <$Pm需要nm个 状态。证据给定N和M，就像第1项的陈述一样，我们定义第三个自动机U如下：• QU=QN×QM。• q0U=（q0N，q0M）.• δU：（QN×QM）×θ→QN×QM定义如下。δU（（qN，qM），x）=（δN（qN，x），δM（qM，x））。• AU=（AN×QM）<$（QN×AM）。自动机U有nm个状态，并且很容易检查它是否识别语言L（N）L（M）。假设n≥1，我们设P n={x∈ N}：|X| {0（mod（n））}我们有x∈Pny当且仅当|X| ≡ |y|（mod（n）），因此我们知道存在一个具有n个识别语言Pn的状态的1DFA。现在，我们考虑序列{P c}。 给定n ≥ 1，存在一个具有n个状态的1DFA，cnn≥1c c语言Pn。 我们可以用汉语的语法来证明Pn<$Pm需要lcm（n，m）态。现在，如果我们假设n和m互质（即gcd（n，m）= 1），我们得到下界nm。Q推论3.4 1DFA没有联合的实态处理。我们知道实态处理隐含着汤普森性质，但考虑到相反的情况不成立，汤普森性质仍然可能对1DFA成立。很容易证明事实并非如此。提案3.5汤普森属性不适用于1DFA。28J.A. 蒙托亚湾Casas/Electronic Notes in Theoretical Computer Science 321（2016）23.Σ证据假设Thompson性质对1DFA成立，那么给定正则表达式α，一定存在一个1DFA，其O（|α|）声明并识别语言L（α）。我们知道这是不可能的，因为正则表达式比1DFA要简洁得多Q我们在上面的证明中使用了正则表达式比1DFA指数级更简洁，这意味着存在一个正则语言序列{Lk}k≥1，存在常数C>1，使得：• 对于所有k，存在一个正则表达式α k，它表示语言L k，其长度在k中是线性的。• 给定k≥1，接受Lk的最小1DFA需要ΩCk态。有许多序列的例子都是这样的，我们包括一个经典的例子，它将在下一节中再次使用。 设={ 0， 1}，k≥1，设Lk为语言，定义为L k={x∈ N}：x [|X| −k + 1] = 1}也就是说：语言Lk是所有字符串的集合，在从右端开始的k个位置处填充1。设k≥1，很容易检查表示语言Lk的正则表达式是表达式（0<$1）<$1（0< $1）k−1，注意这个表达式的长度等于5+（k−1）3。现在考虑由语言Lk确定的等价关系k。我们有x，y在同一个等价类中当且仅当两个字符串的最后k个然后，我们可以声称至少有2k个等价类，这意味着识别Lk的最小1DFA至少有2k个状态。因此，我们知道1DFA的模型不是正确的模型，Thompson属性不适用于它，因为它不能处理真实状态的联合（这似乎是常规操作中更容易处理的），并且，正如我们将看到的，当涉及到处理连接时，它的表现甚至更糟。下一个结果是一个众所周知的结果[11]，但我们发现了一个新的证明，它似乎简单得多定理3.6级联的1DFA-状态复杂度至少是指数的。证据令n ={0， 1}，令{An}n≥1是由下式定义的语言序列：A n={x∈ N}：|X| ≥ 0}注意{An}n≥1是一个常数序列（所有语言都是一样的最后，我们引入第二个序列{Bn}n≥1，其中给定k≥1，语言Bk等于{x∈ N}：x [1] = 1&|X|= k}我们可以证明，对于每个n，对于每个k，等式An·Bk=Lk成立。 也很容易检查：J.A. 蒙托亚湾Casas/Electronic Notes in Theoretical Computer Science 321（2016）2329(i) 对于所有n，语言An可以使用具有唯一内部状态的自动机来识别。(ii) 对于所有n，语言Bn可以使用具有n+2个状态的自动机来识别。(iii) 对于所有n，语言Ln需要2n个状态。总之，我们得到了一个指数下界的处理级联采用1DFA。Q4确定性双向有限状态自动机在本节中，我们研究双向终止确定性有限状态自动机（简称2DFA）模型。设M =（Q，Q，q0，F，δ）是一个一维有限自动机，x = x1x2. x n是一个长度为n的字符串。在输入x上计算M需要n个时间单位，这是工作头到达输入右端所需的时间 现在假设M是一个双向确定性有限自动机，M在输入x上的计算可能是无限的。我们将避免这种可能性，限制自己研究双向终止有限状态自动机，这是双向确定性有限自动机，停止所有输入。如果我们将研究限制在后一种双向自动机类型上，也不会失去一般性，情况是：(i) 没有真正的计算能力损失：双向终止自动机的限制模型可以识别所有的正则语言（任何1DFA都是永远不会移动的2DFA）。(ii) 状态复杂度没有显著的爆炸：任何具有n个状态的双向确定自动机都可以用具有4个n + 1个状态的2DFA来模拟[5]。众所周知，2DFA比1DFA更强大。为了检验这一点，考虑在定理3.6的证明中引入的序列{Ln}n≥1就足够了，注意到Ln可以使用使用n+ 3个状态的2DFA来识别，而任何识别Ln的1DFA都需要2n个状态。有趣的是，可以证明2DFA可能比1NFA更强大。Sakoda和Sipser [8]知道这个事实，他们使用一系列语言证明了这个结果，这些语言在研究Sakoda-Sipser问题（定义活性问题的序列[8]）中起到了重要作用。我们将包括对这一事实的证明，这是基于一个非常简单的语言序列定理4.1存在一个正则语言序列，设{Mn}n≥1，使得.(i) 当n≥1时，存在一个识别Mn的2DFA，它至多使用4个n + 3states.(ii) 如果n≥1，则任何识别Mn的1NFA至少需要2nstates.证据给定n≥ 1，我们设置n={1，...，n}。给定P ={i1，.，i k}[n]，我们定义30J.A. 蒙托亚湾Casas/Electronic Notes in Theoretical Computer Science 321（2016）23P⊆.Σ.ΣP[n]L n={i1，. i k}不。最后，给定n ≥ 1，我们定义M n为语言，w∈N：NP.w∈Ln0Ln−P<$，不难想象出一个终止的2DFA，它有4个n + 3个识别语言M n的状态。现在，我们将证明任何识别Mn的1NFA需要2n个状态。每个Pn可以用一个字符串wP来表示，它对应于按递增顺序写下P的元素因此，我们有2n个不同的弦对，这些对在集合（wP0，w[n]−P）：P<$[n]中，满足以下两个条件：(i) w P0 w[n]−P∈ M n.(ii) 如果PQ，则字符串w P0 w[n]-Q不属于M n。存在这样一组大小为2n的对，意味着任何识别语言Mn的1NFA至少有2n个状态[1]。Q问题4.2我们的证明，以及Sakoda-Sipser的证明，使用了增加的al-phabet。 人们自然会问，在固定的字母表上是否可以实现同样的指数分离。在一元情况下是否也有类似的分离因此，2DFA的模型似乎足够强大，能够有效地模拟非确定性有限自动机。2DFA是否具有常规操作的真实状态处理？定理4.3设M1是一个有m个状态的2DFA，M2是一个有n个状态的2DFA，存在一个2DFA，它能识别语言L（M1）<$L（M2），使用不超过m + n +1个状态。证据 假设Q i是M i的状态集，i = 1，2。我们声称，可以构造一个能识别语言L（M1）<$L（M2）的2DFA N，使得它的状态集等于Q1<$Q2<${q}（我们可以假设，在不损失一般性的情况下，Q1和Q2是不相交的集合，并且q∈/Q1<$Q2）. 这个自动机的计算开始于M1的初始状态，它通过模拟M1来进行，直到达到最终状态（接受或拒绝状态），如果达到的最终状态是接受状态，自动机N停止并接受输入，否则它进入特殊状态q，并开始寻找输入的左端一旦到达左端，自动机N就开始模拟M2的计算. 沿着第二阶段，最终必须达到一个最终状态，如果这个最终状态是接受，自动机接受，否则它拒绝输入。Q现在，我们考虑连接操作。 下一个结果来自[11]：定理4.4设m，n≥ 1，语言Tm= L a m−1（a m）可由m态1DFA识别，但若n与m互质，则串接语言Tn·Tm需要mn个态。上述下限表明，即使在一元的情况下，2DFA也不能进行真实状态的处理级联。因此，看起来真实状态处理J.A. 蒙托亚湾Casas/Electronic Notes in Theoretical Computer Science 321（2016）2331是很难实现的。我们将稍微放松一下我们的问题，考虑以下较弱的问题：问题4.5（无星号表达式）是否存在一种确定性有限自动机模型，它具有无星表达式的实态处理？我们将在本文的剩余部分研究这个新问题，但在此之前，我们将讨论在一元情况下存在超多项式分离（与问题4.2相关）4.6 Landau朗道g（n）= max{lcm（p1，...，p k）：k≥ 1&p1+···+p k≤ n}Landau在研究某些新的理论问题时引入了这一函数lems，他证明了渐近下界g（n）≥e（1+o（1））[11]从[11]。nln（n）. 下一个结果是定理4.7语言Rn= L。ag（n）−1（ag（n））π可以通过以下公式来识别：一个n态的2DFA，但每个接收R n的2DFA至少有（g（n）−1）2个态。从上面的定理我们可以得到的第一个推论是2DFA不能实态处理Kleene星。我们可以得到第二个有趣的推论，它给出了问题4.2的明确答案。推论4.8一元2DFA比一元1NFA在超多项式上更简洁。证据设h1（n）为识别语言Rn的最小1NFA的状态数，h2（n）为识别语言Rn的最小1NFA的状态数. 注意h1（n） =h2（n）。我们将g1（n）定义为识别语言Rn的最小2DFA的状态数，将g2（n）定义为识别语言Rn的最小2DFA的状态数。注意到g1（n）≤n e（1+o（1））n ln（n）≤g2（n）现在，我们使用任何n状态一元1NFA都可以由2DFA模拟，状态数（最多）为二次开销[3]。因此，我们有，（1+o（1））g1（n）ln（g1（n））h1（n）≥e2（1+o（1））mln（m）很明显，函数e2在m中是超多项式，则推论得到了证明。Q注4.9推论4.8表明，在一元世界中，当涉及到常规操作的处理时，2DFA的表现优于1NFA它不应该32J.A. 蒙托亚湾Casas/Electronic Notes in Theoretical Computer Science 321（2016）23被认为是一个大惊喜：回想一下，当涉及到交集和互补运算的处理时，2DFA的表现优于1NFA（参见[9]），这是与三个基本正则运算类似的非正则运算。5确定性双向Pebble自动机无星正则表达式是可以仅使用联合和连接构造的正则表达式，这些表达式构成了一类重要的表达式：这些是表示有限语言的正则表达式。人们可能会认为有限语言很无聊，但他考虑到这些是在编程语言理论中使用最多的形式语言（高效处理正则表达式成为重要任务的领域是否存在一个有限自动机的确定性模型，它具有无星正则表达式的实态处理迄今为止所研究的自动机模型有几个不同的特点，但有一个共同的功能：它们不能写在磁带上。如果我们给这些自动机加上在磁带上写字的能力，我们就可以离开常规世界了。存在一些非常弱的书写形式，这并不迫使2DFA离开常规世界，一个重要的例子是单个鹅卵石提供的书写能力。Ibarra等人[2]研究了一种接受正则语言的卵石自动机模型，Ibarra自动机是双向确定性自动机，它提供了一个卵石，这些自动机使用它来标记磁带上的细胞（定义见[2]）。我们使用符号1p2DFA来表示遵循以下进一步限制的Ibarra自动机类：设M为1p2DFA。它有两个初始状态，真实的初始状态第一种特殊状态称为L-初始状态，第二种特殊状态称为R-初始状态。假设单元i是卵石的当前位置，并且假设工作台位于单元j上，其中j

下载后可阅读完整内容，剩余1页未读，立即下载