涿州400电话申请开通【涿州企业网站建设】涿州微信公众号小程序开发运营价格、涿州微信公众号APP软件客户端设计运营、涿州网页页面设计公司费用、涿州公司网站制作方案流程改版维护大概需要多少钱

涿州400电话申请开通【涿州企业网站建设】涿州微信公众号小程序开发运营价格、涿州微信公众号APP软件客户端设计运营、涿州网页页面设计公司费用、涿州公司网站制作方案流程改版维护大概需要多少钱

涿州市，古称涿鹿、涿邑、涿郡、范阳、涿州路、涿县。河北省保定市代管县级市。 [1]  地处河北省中部、保定市北部，地处京、津、保三角地带，京畿南大门。区位优势得天独厚，地质构造属太行山山洪冲积扇，地势平坦，土质肥沃，拥有丰富的水利、地热和沙石料资源，古有“幽燕沃壤"， “督亢膏腴"之称。

涿州市总面积742.5平方千米。截至2019年3月，涿州市户籍总人口70.15万。涿州市辖3个街道、10个镇、1个乡，另设有高新技术产业开发区和京南经济开发区。 [2]  市政府驻双塔街道范阳西路51号。

1986年9月24日，经国务院批准撤销涿县，设立涿州市（县级市）。 [3]  2008年，涿州市被河北省人民政府批准为“省级历史文化名城”。 [4]  2019年12月6日，涿州市入选“2019年投资潜力全国百强县（市）”。 [5] 

2018年，涿州市地区生产总值完成379.2亿元，同比增长6.1%；其中，第一产业增加值21.8亿元，同比增长3.5%；第二产业增加值140.2亿元，同比增长4.8%；第三产业增加值217.2亿元，同比增长7.3%。人均地区生产总值为61054元，同比增长5.7%。 [6]  2021年3月，被授予 2020年河北省村庄清洁行动先进县（市、区）。

示例 10.10

图10-17中的非确定自动机有4个状态，而图10-20中与它等价的确定自动机也有4个状态。如果所有的非确定自动机都能转换成小型确定自动机就好了，例如，在编译编程语言中常用到的某些自动机其实可以转换成相当小的确定自动机。不过，不能保证确定自动机一定很小，具有k个状态的非确定自动机有可能最终被转换成状态多达2k 个的确定自动机。也就是说，对非确定自动机状态集的幂集中的每个成员，确定自动机都有相应的状态。

举个会得到很多状态的例子，考虑一下10.3节图10-14中的自动机。因为该非确定自动机有20种状态，可以想象一下，通过子集构造构建的确定自动机可能有约220个，或者说是超过100万个状态，这些状态全都是{0,1,…,19}的幂集的成员。实际结果并没有这么糟，但也存在相当多的状态。

我们不会尝试画出与图10-14中非确定自动机等价的确定自动机。不过，可以考虑一下实际上需要哪些状态集。首先，因为对每个字母都有从状态0到其自身的转换，所以实际看到的所有状态集都包含0。如果字母a尚未输入，就不能到达状态1。不过，如果刚好已经看到一个a，不管还看到些什么，我们都将在状态1中。我们还可以为washington中其他任何字母得出相似的论断。

如果在状态0中开始图10-14，并为其提供属于washington中所出现字母的子集的一列字母，然后除了在状态0中之外，还可以在状态1、3、5、7、9、12、14、16和18的某个子集中。通过恰当地选择输入字母，我们可以安排在这些状态集的任意一个中。因为有29=512个这样的集合，所以在与图10-14等价的确定自动机中至少有这么多个状态。

不过，其中的状态要更多，因为字母n在图10-14中得到了特殊处理。如果在状态9中，我们还可以在状态10中，而且如果已经看到两个n，其实就将同处状态9和状态10中。因此，尽管对其他8个字母来说都只有两个选择（比如，对字母a，要包含状态1，要么不含状态1），而对字母n来说，共有3种选择（既不含状态9也不含状态10、只包含状态9，或者同时包含状态9和状态10）。因为至少存在3×28=768种状态。

不过这并非全部。如果到目前为止的输入以washington中的字母之一结束，而且我们之前已经看到足够多的该字母，那么我们也应该在对应该字母的接受状态中，比方说，对a来说就是状态2。然而，我们在处理相同输入后不可能在两个接受状态中。为增加的状态集计数变得更麻烦了。

假设接受状态2是该集合的成员。那么可知1也是该集合的成员，0当然也是，不过我们仍然对与除a之外的字母对应的状态拥有所有选择，这类集合的数量是3×27，或者说是384。如果我们的集合包含接受状态4、6、8、13、15、17或19，这样的道理也同样实用，在每种情况中都有384个集合包含相应的接受状态。唯一的例外就是含接受状态11（就是状态9和状态10也出现）的情况。在该情况下，只有28＝256种选择。因此，该等价确定自动机的状态总数为：

768+8×384+256＝4864

第一项768表示那些不含接受状态的集合的数量。接下来的一项，表示的是分别包含与除n之外其他8个字母对应的接受状态的8类集合的数量，第三项256则表示含状态11的集合的数量。

关于子集构造的想法

子集构造是相当不好理解的。特别是确定自动机的状态可以是非确定自动机的状态集这一思路可能需要大家耐心思考才能想通。不过，这种把结构化对象（状态集）与原子对象（确定自动机的各个状态）融合成同一对象的概念，是计算机科学中的一种重要概念。我们已经在程序中看到过这一概念，而且经常必须用到它。例如，函数的参数，比方说L，表面上看是原子的，而对其进行更仔细的检查可能发现它是有着复杂结构的对象，比如，具有连接到其他记录的字段从而能形成表的记录。同样，图10-20中确定自动机D 的状态{0，2}也可以用简单的名称“5”或“a”来代替。

10.4.3　子集构造起效的原因

很明显，如果D 是利用子集构造从非确定自动机N 构建的，那么D 就是确定自动机。原因在于，对每个输入符号x 和D 的每个状态S 而言，我们定义了D 的某特定状态T，它满足从S 到T 的转换的标号中包含x。不过如何得知自动机N 和D 是等价的呢？也就是说，我们需要知道，对任意输入序列a1a2…ak，当且仅当N 接受a1a2…ak 时，在下列情况下，自动机D 到达的状态S 是种接受状态。

1. 从起始状态开始；

2. 并且沿着标记为a1a2…ak 的路径行进。

请记住，当且仅当从N 的起始状态有一条标记为a1a2…ak 的路径能到达N 的某个接受状态时，N 才会接受a1a2…ak。

D 所做的事情与N 所做的事情之间的联系就更紧密了。如果D 具有从它的起始状态到标记为a1a2…ak 的状态的路径，那么被视为自动机N 的某个状态集的集合S，就刚好是从N 的起始状态开始沿着某标记为a1a2…ak 的路径所能到达的状态组成的集合。这种关系如图10-21所示。因为我们已经定义了，只有在S中的某一成员是N 的接受状态时，S才是D的接受状态，所以要得出D和N都接受a1a2…ak 或都不接受a1a2…ak，也就是要得出D 和N 是等价的，就只需要图10-21所示的关系。

图 10-21　非确定自动机N 的操作与对应的确定自动机D 的操作间存在的关系

我们需要证明图10-21所示的关系，该证明要对输入字符串长度k 进行归纳。需要通过对k 的归纳来证明的正式命题是，从D 的起始状态开始沿着标记为a1a2…ak 的路径到达的状态{s1，s2，…，sn}，刚好是从N 的起始状态开始沿着标记为a1a2…ak 的路径到达的状态构成的集合。

依据。设k=0。长度为0的路径将我们留在出发的位置，也就是，在自动机D 和N 的起始状态中。回想一下，如果s0是N 的起始状态，D 的起始状态就是{s0}。因此该归纳命题对k=0来说成立。

涿州400电话申请开通【涿州企业网站建设】涿州微信公众号小程序开发运营价格、涿州微信公众号APP软件客户端设计运营、涿州网页页面设计公司费用、涿州公司网站制作方案流程改版维护大概需要多少钱