迁安市网站推广【迁安市办理400电话】迁安市SEO优化、迁安市微信公众号APP客户端小程序开发、迁安市网站托管、迁安市APP开发

迁安市网站推广【迁安市办理400电话】迁安市SEO优化、迁安市微信公众号APP客户端小程序开发、迁安市网站托管、迁安市APP开发

迁安市，河北省直辖县级市，由唐山市代管，位于河北省东北部，燕山南麓，滦河岸边，介于东经118°37′～118°55′，北纬39°51′～40°15′之间，市境纵跨直线距离45公里，横跨直线距离39公里。东隔青龙河与秦皇岛市卢龙县相望，南与滦州市相邻，西接迁西县，北以长城为界与秦皇岛市青龙满族自治县毗邻，全市总面积1227平方公里。 [1]  市人民政府驻地永顺街道 [2]  。

迁安市境内地势西北高，东南低，属暖温带、半湿润季风性气候，境内主要风景区有迁安博物馆、白羊峪、黄台山公园和黄台湖等。 [3] 

迁安西距北京市220公里、距天津市190公里、距唐山市80公里，东距秦皇岛市110公里，北距承德市170公里，南距京唐港100公里。临近京唐港、曹妃甸港、天津新港、秦皇岛港。境内北京－哈尔滨高速公路、北京－秦皇岛高速公路、102国道、三抚公路和津山铁路、大秦铁路、通坨铁路横贯东西，冷大公路、卑水铁路、迁曹铁路纵穿南北。津秦高铁在迁安设有客运站，即滦河站。

迁安先后被授予全国文明城市、国家卫生城市、国家园林城市、中国宜居城市、世界健康城市、全国绿化模范城市、全国生态建设突出贡献单位等称号，是首批国家海绵城市试点中唯一的县级市、首批国家智慧城市试点单位。 [4]  2019年10月，入选2019年度全国投资潜力百强县市、2019年度全国新型城镇化质量百强县市。 [5-6]  2020年10月，入选河北省第一批新型智慧城市建设试点名单。 [7]  2020年12月，社科院发布《全国县域经济综合竞争力100强》，迁安排名第23 [8]  。

10.3　确定自动机和非确定自动机

使用自动机进行的最基本的操作之一是接受一系列的符号a1a2…ak，并从起始状态起循着一条由标号依次为这些符号的弧组成的路径行进。也就是说，对i=1、2、…、k 来说，ai 都是集合Si 中作为路径上第i 条弧标号的成员。构建这一路径及其状态序列的过程就是自动机对输入序列a1a2…ak 的模拟（simulating）。可以说这一路径标号为a1a2…ak，当然，它也可能有其他标号，因为给路径上的弧提供标号的各集合Si 可能各自含有很多字符。

示例 10.3

我们在图10-5中进行过一次这样的模拟，其中模仿了图10-4中的自动机对序列0101101的处理。另外，以图10-3中用来识别单词中是否含有序列aeiou的自动机为例，考虑对字符串adept的处理。

我们从状态0中开始。从状态0出发的转换有两次，一次是针对字符集Λ-a的转换，另一次是针对单独一个字母a的。因为adept的第一个字符就是a，所以要遵循后一个转换，这把我们带到了状态1。从状态1出发，又有针对Λ-e和e的转换。因为第二个字符是d，所以必须遵循前一种转换，因为Λ-e包含除了e之外的所有字母。这把我们再次留在状态1中。因为第三个字母是e，所以要循着从状态1出发的第二种转换，将我们带到状态2。adept的最后两个字母都在集合Λ-i中，所以下两次转换都是从状态2到状态2。因此在状态2中就完成了对adept的处理。相应的状态转换序列如图10-6所示。因为状态2不是接受状态，所以我们没有接受输入adept。

图 10-6　对10-3中的自动机针对输入adept的模拟

有关自动机输入的术语

在这里将要讨论的例子中，自动机的输入是字符，比如字母和数字，而且将输入当作字符并将输入序列当作字符串是很方便的。我们在这里一般会使用这一术语，不过偶尔会将“字符串”简称为“串”。不过，在有些应用中，自动机要转换的输入是从比ASCII字符集更广泛的集合中选出的。例如，编译器可能会把while这样的关键词看作单个输入符号，我们将这种情况用加粗的字符串while表示。因此有时候我们会把这种单独的输入称作“符号”而非“字符”。

10.3.1　确定自动机

在10.2节中讨论过的自动机有个重要的属性。对任意状态s 和任意输入字符x 来说，至多只有一种从状态s 出发的转换的标号中含有x。这样的自动机就称为确定自动机。

为给定输入序列模拟确定自动机是很简单的。在任意状态s 中，给定下一个输入字符x，考虑从s 出发的每种转换的标号。如果我们找到标号含x 的转换，那么该转换就指向适当的下一个状态。如果没有含x 的转换，那么该自动机就“死机”了，而且不能再继续处理输入，就像图10-3中的自动机在到达状态5后就会停机那样，因为它知道自己已经找到了子序列aeiou。

将确定自动机转变为程序是很容易的。我们为每个状态编写一段代码。对应状态s 的代码会检查它的输入，并决定应该遵循从s 出发的哪种转换（如果存在这样的转换）。如果选定了从状态s 到状态t 的转换，那么必须安排表示状态t 的代码接着表示状态s 的代码执行，可能是通过goto语句来实现。

示例 10.4

这里我们编写了一个对应图10-4所示反弹过滤器自动机的函数bounce()。变量x是用来从输入中读字符的。状态a、b、c 和d 将分别用标号a、b、c和d来表示，而且要使用标号finis表示程序的结尾，也就是在输入中遇到0和1之外的字符时会到达的地方。

代码如图10-7所示。例如，在状态a 中我们会打印字符0，因为a 是非接受状态。如果输入字符是0，就停留在状态a，而且如果输入字符是1，就进入状态b。

void bounce(){
         char x;

         /* 状态 a */a:       putchar('0');
         x = getchar();
         if (x == '0') goto a; /* transition to state a */
         if (x == '1') goto b; /* transition to state b */
         goto finis;

         /* 状态 b */b:       putchar('0');
         x = getchar();
         if (x == '0') goto a; /* transition to state a */
         if (x == '1') goto c; /* transition to state c */
         goto finis;

         /* 状态 c */c:       putchar('1');
         x = getchar();
         if (x == '0') goto d; /* transition to state d */
         if (x == '1') goto c; /* transition to state c */
         goto finis;

         /* 状态 d */d:       putchar('1');
         x = getchar();
         if (x == '0') goto a; /* transition to state a */
         if (x == '1') goto c; /* transition to state c */
         goto finis;finis:   ;}复制代码

图 10-7　实现图10-4中确定自动机的函数

在“自动机”的定义中没有要求从某给定状态出发的转换的标号必须是不相交的，如果集合没有相同的成员则说它们是不相交的，即它们的交集为空。如果有图10-8所示的这种图，其中针对输入x 有从状态s 到状态t 和状态u 的转换，这样一来该自动机要如何用程序来实现就不是很清楚了。也就是说，在执行对应状态s 的代码时，如果发现x 是下一个输入字符，就得知接下来一定要进入表示状态t 的代码的开头，而且还要进入表示状态u 的代码的开头。因为程序一次不能到达两个位置，所以要如何模拟从状态出发的转换具有相同标号的自动机是很不明朗的。

图 10-8　从状态s 出发的针对输入x 的非确定转换

10.3.2　非确定自动机

非确定自动机可以具有从某一状态出发的包含相同符号的两个或多个转换，但这不是必须的。请注意，严格地讲，确定自动机也是一种非确定自动机，它只是刚好没有针对同一符号的多种转换。一般来说“自动机”都是不确定的，不过我们在强调自动机不是确定自动机时还是会使用“非确定自动机”的说法。

正如上文提过的，非确定自动机不能直接用程序实现，不过它们对这里将要讨论的若干应用来说是很实用的概念工具。此外，通过利用10.4节中将要介绍的“子集构造”，可以将任意非确定自动机转换成接受相同字符串集合的确定自动机。

10.3.3　非确定自动机的接受

在我们试图模拟针对输入字符串a1a2…ak的非确定自动机时，可能发现同一个字符是多条路径的标号。习惯上讲，如果至少有一条由某输入编辑的路径可以通向接受状态，就可以说非确定自动机接受这一输入字符串。以接受状态结尾的那一条路径，要比任意数量以非接受状态结尾的路径更重要。

不确定性和猜测

认为不确定性让自动机可以“猜测”是种看待不确定性的实用方式。如果我们不知道在某给定状态中要对某给定的输入字符做什么，就可以对下一个状态做出若干选择。因为由带向接受状态的字符串标记的任意路径会被解释为接受，所以非确定自动机其实被赋予了进行一次正确猜测的信用，而不管它还会造成多少次错误猜测。

迁安市网站推广【迁安市办理400电话】迁安市SEO优化、迁安市微信公众号APP客户端小程序开发、迁安市网站托管、迁安市APP开发