涿州网站制作【涿州网站优化】涿州建网站、涿州微信公众号运营、涿州网页设计、涿州微信小程序商城

涿州网站制作【涿州网站优化】涿州建网站、涿州微信公众号运营、涿州网页设计、涿州微信小程序商城

涿州市，古称涿鹿、涿邑、涿郡、范阳、涿州路、涿县。河北省保定市代管县级市。 [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.2.1　状态机的图表示

我们可以把图10-2中这种程序的行为用图表示出来，其中图的节点表示该程序的各个状态。更重要的可能在于，可以通过设计图从而设计出程序，并机械化地将图转化成程序，要么自己动手做，要么利用某种为这个目的编写的程序设计工具。

表示程序状态的图都是有向图，它们的弧都是用字符集标记的。如果当我们在状态s 时，刚好只有当看到集合C 中的一个字符时才能行进到状态t，就存在从状态s 到状态t 的标号为字符集C 的弧。这些弧叫作转换（transition）。如果x 是字符集C 中的某个字符，它标记了从状态s 到状态t 的转换，就说“进行了针对x 的到状态t 的转换”。在集合C 为单元素集{x }这种常见的情况下，我们会使用x 作为该弧的标号，而不用{x }。

我们还会给某些节点标记接受状态（accepting state）。当到达这些状态之一时，就找到了模式并要“接受”它。按照惯例，接受状态是用双层圆圈表示的。最后，这些节点之一会被指定为起始状态，也就是开始模式识别过程所在的状态。我们用一条不知道来自何方的进入箭头表示起始状态。这样的图就被称为有限自动机，或就叫自动机。在图10-3中可以看到自动机的一个例子。

图 10-3　识别含子序列aeiou的字符序列的自动机

从概念上讲，自动机的行为其实很简单。可以想象，自动机接收一列已知字符作为输入序列。它从起始状态开始读输入序列的第一个字符。根据第一个字符的不同，它进行的转换可能是转换到同一状态，也可能是转换到另一状态。这种转换可用自动机的图来表示。然后自动机会读第二个字符，并作出合适的转换，等等。

示例 10.1

对应图10-2中testWord函数的自动机如图10-3所示。在该图中，我们使用了下面都要遵守的一个约定，用希腊字母Λ（拉姆达）代表所有大写字母和小写字母组成的集合。还要用Λ-a这样的简写形式表示除a之外所有大小写字母组成的集合。

节点0是起始状态。针对除了a之外的任意字母，我们都会保持状态0，不过遇到a就要进入状态1。同样，一旦到达状态1，就会停留在状态1，除非看到e，在看到e的情况下就要进入状态2。接下来，当看到i然后看到o时就分别到达状态3和状态4。除非看到u并进入唯一的接受状态——状态5，否则我们会停留在状态4中。再没有任何从状态5出发的转换了，因为我们不再检测待测单词的其余字符，而是要返回TRUE，声明我们已成功完成测试。

在状态0到状态4中遇到空白（或其他非字母字符）也是没有价值的，我们不会进行任何转换。在这种情况下，处理会停止，而且，因为我们现在未到达接受状态，所以会拒绝该输入。

示例 10.2

接下来的例子来源于信号处理。这里不再把所有字符作为自动机可能接收到的输入，而是只允许输入0和1。我们要设计的这种特殊自动机有时也称为反弹过滤器（bounce filter），它接受0和1组成的序列作为输入。该自动机的目的就是“平滑”该序列，方法是将由1包围的一个0当作“噪音”，并把这个0替换为1。同样，由0包围的一个1也会被当作噪声并被0替代。

这里举一个反弹过滤器使用方式的例子，我们可以逐行扫描某数字化的黑白图像。该图像的每一行其实都是0和1组成的序列。因为图片有时候会因胶片瑕疵或拍摄问题造成有一些小点颜色错误，所以，为了减少图像中不同区域的数量，并让我们将精力放在“真实”的特色而非那些虚假的特征上，消除这样的点是很实用的。

图10-4表示的就是对应该反弹过滤器的自动机。其中的4种状态解释如下：

(a) 我们已经看到至少在一行中含两个0的一列0；

(b) 我们已经看到一列0后面跟着一个1；

(c) 我们已经看到至少有两个1的一列1；

(d) 我们已经看到一列1后面跟着一个0。

状态a 被指定为起始状态，表示我们的自动机进行处理时就好像在输入之前有一个看不见的前缀0序列那样。

图 10-4　消除虚假的0和1的自动机

接受状态是c 和d。对该自动机而言，其接受过程与图10-3所示的自动机有着一些不同的含义。对图10-3所示的自动机而言，在到达接受状态时，就可以说整个输入都被接受了，包括自动机还没有读到的那些字符。1而在这里，我们想要接受状态表述“输出一个1”，还要一个表述“输出一个0”的非接受状态。在这种解释下，我们会将输入中的每一位都转化成输出中的每一位。通常输出是和输入相同的，不过有时候也会不同。例如，图10-5展示了输入为0101101时的输入、各个状态和它们的输出。

1不过，通过为状态5加一个所有字母上的转换，我们可以修改该自动机，使其能继续读u之后的所有字母。

图 10-5　图10-4中的自动机处理输入0101101时的情况模拟

我们从状态a 开始，因为a 是非接受状态，所以输出0。请注意，这一初始输出并不是对任意输入的回应，而是表示在初次开启设备时自动机的条件。

图10-4中从状态a 出发标记了输入0的转换是到达状态a 自身的。因此第二个输出还是0。第二个输入是1，而且从状态a 可以进行针对1的到状态b 的转换。该状态“记住了”我们已经看到过一个1，不过因为b 是非接受状态，所以输出仍然是0。针对第三个输入，也就是另一个0，我们又从状态b 回到了状态a，而且继续发出输出0。

接下来的两个输入都是1，可以先将自动机带到状态b，然后带到状态c。对这两个1中的第一个1，我们发现自己是在状态b 中，这会带来输出0。这个输出是错的，因为我们其实已经开始处理1了，但是在读完第四个输入后还不知道这一点。这种简单设计的影响在于，不管是0还是1组成的，所有的串都被右移了一位，因为在自动机意识到它已经开始处理新的串而不是“噪声”位之前，一行中已经接受了2位。在接收第5个输入时，我们就会遵循从状态b 到状态c 针对输入1的转换。在这一情况下，会得到第一个1输出，因为c 是接受状态。

最后两个输入是0和1。0把我们从状态c 带到状态d，这样我们可以记得自己已经看到了一个0。从状态d 的输出依然是1，因为该状态是接受状态。最后的1将我们带回状态c 并生成输出1。

自动机与其程序之间的区别

自动机是种抽象。从10.3节起将会变得明确，通过确定从起始状态到某个用相应序列标记的接受状态之间是否存在路径，自动机呈现了一种对任意输入字符序列的接受/拒绝决定。举例来说，图10-5表示的反弹过滤器自动机的行为告诉我们，该自动机拒绝ε、0、01、010和0101这些前缀，但它接受01011、010110和0101101这几个前缀，如图10-4所示。图10-3的自动机接受abstemiou这样的字符串，但拒绝abstemious，因为从状态5没办法到达最后的s。

另一方面，由自动机创建的程序能以多种方式使用这种接受/拒绝决定。例如，图10-2中的程序使用了图10-3所示的自动机，但它不是认可标记通向接受状态的路径的字符串，而是认可整行输入，也就是，接受abstemious而非abstemiou。这是绝对合理的，而且反映了我们编写程序测试按次序的5个元音字母的方式，而不管是使用了自动机或是其他的方法。据推测，只要我们到达字母u，该程序就会打印出整个单词而不再继续检查其余字母。

图10-4所示自动机的使用方式就更简单。我们将会看到，图10-7中对应这一反弹过滤器的程序会直接把每个接受状态转化成打印一个1的行动，而将每个拒绝状态转化成打印一个0的行动。

涿州网站制作【涿州网站优化】涿州建网站、涿州微信公众号运营、涿州网页设计、涿州微信小程序商城