涿州网站建设【涿州网络公司】涿州做网站、涿州微信公众号开发、涿州网站设计、涿州小程序制作

涿州网站建设【涿州网络公司】涿州做网站、涿州微信公众号开发、涿州网站设计、涿州小程序制作

涿州市，古称涿鹿、涿邑、涿郡、范阳、涿州路、涿县。河北省保定市代管县级市。 [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年河北省村庄清洁行动先进县（市、区）。

模式是具有某个可识别属性的对象组成的集合。字符串集合就是一类模式，比如C语言合法标识符的集合，其中每个标识符都是个字符串，由字母、数字和下划线组成，开头为字母或下划线。另一个例子是由只含0和1的给定大小数组构成的集合，读字符的函数可以将其解释为表示相同符号。图10-1就展示了全都可以解释为字母A的3个7×7数组。所有这样的数组就可以构成模式“A”。

0001000　　　0000000　　　0001000
0011100　　　0010000　　　0010100
0010100　　　0011000　　　0110100
0110110　　　0101000　　　0111110
0111110　　　0111000　　　1100011
1100011　　　1001100　　　1000001
1000001　　　1000100　　　0000000

图 10-1　模式“A”的3个实例

与模式相关的两个基本问题是它们的定义与它们的识别，这是本章以及第11章的主题。模式的识别是诸如图10-1所示的光学字符识别（Optical Character Recognition，OCR）这样的任务中不可或缺的一部分。在某些应用中，程序中模式的识别是编译过程，也就是将程序从一种语言（比方说C语言）翻译成另一种语言（比如机器语言）的过程的一个重要部分。

模式应用在计算机科学中还有其他很多例子。模式在设计用于组成计算机和其他数字设备的电子电路的过程中扮演着关键的角色。它们也可以用在文本编辑器中，让我们可以查找特定单词或特定字符串集合的实例，比如“字母if之后跟着任意由then开头的字符序列”。大多数操作系统允许用户在命令中使用模式，例如，UNIX命令“ls *tex”就会列出所有以3字符序列“tex”结尾的名称。

人们围绕着模式的定义和识别建立起了一套庞大的知识体系。这一理论被称为“自动机理论”或“语言理论”，而其基本定义和技术都是计算机科学的核心部分。

10.1　本章主要内容

本章处理的是由字符串集合组成的模式，我们在本章中将会学习以下内容。

• “有限自动机”是一种基于图的模式指定方式。有限自动机又分为两种：确定自动机（10.2节）和非确定自动机（10.3节）。

• 可以用简单的方法把确定自动机转换成识别其模式的程序（10.2节）。

• 可以利用10.4节介绍的“子集构造”，把非确定自动机转换成识别相同模式的确定自动机。

• 正则表达式是种代数，用来描述可由自动机描述的同类模式（10.5节到10.7节）。

• 正则表达式可转换为自动机（10.8节），反之亦然（10.9节）。

我们还要在第11章中讨论串模式，其中会引入一种名为“上下文无关文法”的递归表示法来定义模式。我们将看到这种表示法可以描述没法用自动机或正则表达式表示的模式。不过，在很多情况下，文法都不如自动机或正则表达式那样容易转换为程序。

10.2　状态机和自动机

用来查找模式的程序通常有着特殊的结构。我们可以在代码中确定某些位置，在这些位置可以得知与程序寻找模式实例的过程有关的特殊信息。我们将这些位置称为状态。而程序的整体行为可以视作程序随着读入输入从一种状态转移到另一种状态。

要让这些概念变得更具体，可以考虑一个具体的模式匹配问题：“哪些英语单词按次序含有5个元音字母？”要回答这一问题，可以使用很多操作系统中都能找到的单词表。例如，在UNIX系统中可以在文件/usr/dict/words中找到这样的表，表中每一行都含有一个常用单词。在该文件中，一些含多个元音字母的单词是按以下次序排列的：

abstemiousfacetious
sacrilegious复制代码

我们来编写一个简单的C语言程序，检查某个字符串并确定5个元音字母是否按次序出现在该字符串中。从字符串的开头开始，该程序首先会查找到a。我们会说该程序处于“状态0”，直到它发现一个a，然后它就进入“状态1”。在状态1中，它会查找字母e，而且当它找到一个之后，就会进入“状态2”。该程序会继续按照这种方式运行，直至到达查找字母u的“状态4”。如果它找到u，那么该单词就是按次序含有5个元音字母，这个程序就能进入一个用于接受的“状态5“。不需要再扫描单词的其余部分，因为已经可知，不管u后面有哪些字母，该单词都是满足条件的。

可以这样解释状态i，就是对i=0、1、…、5，程序已经按次序遇到了前i个元音字母。这6个状态总结了程序在从左到右扫描其输入的过程中需要记住的所有内容。例如，在状态0中，尽管该程序在查找a，但它不需要记住是否已经看到了e。原因在于这样的e不可能先于任何a，因此不能作为序列aeiou中的e。

这种模式识别算法的核心是图10-2中的findChar(pp,c)函数。该函数的参数是pp——指向字符串的指针的地址，以及所需的字符c。也就是说，pp是“指向指向字符的指针的指针”。函数findChar会查找字符c，并且顺便会移动已给定地址的指针，直到该指针指向超过字符c或该串结尾的位置。它返回BOOLEAN类型的值，就是我们定义的与int相同的类型。正如在1.6节中讨论过的，我们预期BOOLEAN类型的值只有TRUE和FALSE，它们分别被定义为1和0。

在第(1)行，findChar会检查当前由pp指示的字符。如果它既不是所需的字符c，也不是C语言中标记字符串末端的字符“\0”，那么在第(2)行我们会移动pp指向的该指针。第(3)行的测试会确定我们是否因为遍历完该串而停止。如果是，就返回FALSE，否则前移该指针并返回TRUE。

      #include <stdio.h>

      #define TRUE 1
      #define FALSE 0
      typedef int BOOLEAN;

      BOOLEAN findChar(char **pp, char c)
      {
 (1)      while (**pp != c && **pp != '\0')
 (2)          (*pp)++;
 (3)      if (**pp == ’\0’)
 (4)          return FALSE;
          else {
 (5)          (*pp)++;
 (6)          return TRUE;
          }
      }

      BOOLEAN testWord(char *p)
      {
          /* 状态 0 */
 (7)      if (findChar(&p, 'a'))
              /* 状态 1 */
 (8)          if (findChar(&p, 'e'))
                  /* 状态 2 */
 (9)              if (findChar(&p, 'i'))
                      /* 状态 3 */(10)                  if (findChar(&p, 'o'))
                          /* 状态 4 */(11)                      if (findChar(&p, 'u'))
                              /* 状态 5 */(12)                          return TRUE;(13)      return FALSE;
      }

      main()
      {(14)      printf("%d\n", testWord("abstemious"));
      }复制代码

图 10-2　找到带有子序列aeiou的单词

在图10-2中，接下来是testWord(p)函数，它可以区分由p指向的字符串是否按次序含有所有元音字母。该函数在第(7)行前从状态0开始。在该状态中它在第(7)行调用findChar，其中第二个参数是a，用来查找字母a。如果它找到了a，findChar就会返回TRUE。因此在第(7)行如果findChar返回了TRUE，程序就会转移到状态1，其中在第(8)行会对e进行相似的测试，从第一个a之后开始扫描该字符串。因此它会继续查找元音字母，直到第(12)行，如果它找到了字母u，就会返回TRUE。如果有任何一个元音字母未被找到，控制权就会转移到第(13)行，在该行中testWord会返回FALSE。

第(14)行的主程序会测试特定的字符串“abstemious”。在实践中，我们可能会对文件中的所有单词反复使用testWord，以找出那些按次序含有5个元音字母的单词。

涿州网站建设【涿州网络公司】涿州做网站、涿州微信公众号开发、涿州网站设计、涿州小程序制作