一. 枚举类型
枚举类型可以声明符号名称来表示 int 整形常量，枚举类型的目的是提高程序的可读性。
默认情况下，枚举列表中的常量是从 0 开始赋予的；也可以为枚举常量指定整数值
#include <stdio.h>
enum States
{
state_0, //0
state_1, //1
state_2, //2
};
enum
{
state_3 = 3, //3
state_4, //4
state_5, //5
};
int main(void)
{
printf("%d\n" , state_0);
printf("%d\n" , state_1);
printf("%d\n" , state_2);
printf("%d\n" , state_3);
printf("%d\n" , state_4);
printf("%d\n" , state_5);
return 0;
}
二. switch 语句
switch 语句的作用也是在多个选项中选择，虽然这可以用 if 语句实现，但在某些场合下，switch 语句更为方便
switch 语句语法
switch(expression)
{
statement-list
}
贯穿于语句列表之间的是一个或多个 case 标签
case constant-expression:
常量表达式是指在编译期间进行求值的表达式，它不能是任何变量
不同寻常的是 case 标签并不把语句列表划分为几个部分，它们只是确定语句列表的进入点
#include <stdio.h>
enum Fruit
{
apple,
banana,
orange,
pear
};
int main(void)
{
int fruit = apple;
switch(fruit)
{
case apple:
printf("I'm an apple.\n");
case banana:
printf("I'm a banana.\n");
case orange:
printf("I'm an orange.\n");
case pear:
printf("I'm a banana.\n");
default:
printf("No such fruit.\n");
}
return 0;
}
如果 switch 语句的执行遇到了 break 语句，执行流就会立即跳到语句列表的末尾。
否则，执行流从语句列表中 case 标签值与 expression 值匹配的语句，直到语句列表的结束，它们之间所有的语句均被执行。
#include <stdio.h>
enum Fruit
{
apple,
banana,
orange,
pear
};
int main(void)
{
int fruit = apple;
switch(fruit)
{
case apple:
printf("I'm an apple.\n");
break;
case banana:
printf("I'm a banana.\n");
break;
case orange:
printf("I'm an orange.\n");
break;
case pear:
printf("I'm a banana.\n");
break;
default
printf("No such fruit.\n");
break;
}
return 0;
}
当表达式的值与所有的 case 标签的值都不匹配，就会执行 default 子句。
default 子句可以写在任何一个 case 标签出现的位置，这使得我们可以执行那些与 case 标签不匹配的表达式
#include <stdio.h>
enum Fruit
{
apple,
banana,
orange,
pear
};
int main(void)
{
int fruit = 999;
switch(fruit)
{
default:
printf("No such fruit.\n");
case apple:
printf("I'm an apple.\n");
case banana:
printf("I'm a banana.\n");
case orange:
printf("I'm an orange.\n");
break;
case pear:
printf("I'm a banana.\n");
break;
}
return 0;
}
三. 有穷自动机简介
有穷自动机是许多重要类型的硬件和软件的有用模型
- 数字电路的设计和性能检查软件
- 编译器的 “词法分析器”
- 扫描大量文本来发现单词、短语出现的软件
- 只有有穷多个不同状态的系统（比如通信协议或安全交换信息的协议）的验证软件
自动机理论的中心概念
1.1 字母表
字母表是符号的有穷非空集合。约定俗成，用符号 $\sum$ 表示字母表。常见字母表包括：
- $\sum = \{0, 1\}$，二进制字母表
- $\sum = \{a, b, \cdots, z\}$，所有小写字母的集合
1.2 串
串是从某个字母表中选择的符号的有穷序列。例如，01101 是从二进制字母表 $\sum = \{0, 1\}$ 中选出的串，串 111 是从这个字母表中选择的另一个串
1.2.1 空串
空串是出现 0 次符号的串，这个串记作 $\epsilon$，是可从任意字母表中选择的串
1.2.2 串的长度
串的长度就是串中符号的位数。例如，01101 长度为 5。
串 w 的长度的标准记号是 $\lvert w \rvert$ 。例如， $\lvert 011 \rvert$ = 3，$\lvert \epsilon \rvert$ = 0
1.2.3 字母表的幂
如果 $\sum$ 是一个字母表，就可用指数记号来表示这个字母表某个长度的所有串的集合。定义 $\sum^{k}$ 是长度为 k 的串的集合，串的每个符号都属于 $\sum$
注意无论 $\sum$ 是什么字母表，$\sum^{0}$ = $\{ \epsilon \}$ 。就是说，$\epsilon$ 是长度为 0 的唯一的串
如果 $\sum = \{0, 1\}$，则 $\sum^{1}=\{0, 1\}$，$\sum^{2}=\{00， 11，01，10\}$，$\sum^{3}=\{000， 001，010，011，100，101，110，111\}$，依次类推。
字母表 $\sum$ 上所有串的集合约定记作 $\sum^{\ast}$ ，换句话说 $\sum^{\ast}=\sum^{0}\bigcup\sum^{1}\bigcup\sum^{2}\bigcup\cdots$
1.2.4 串的连接
设 x 和 y 都是串。于是，xy 表示 x 和 y 的连接。设 x = 01101 且 y = 110，则 xy = 01101110，yx = 11001101。对任意串 w，等式 $\epsilon w$=$w\epsilon$=$w$ 成立。
1.3 语言
$\sum$ 是某个具体的字母表，全部从 $\sum^{\ast}$ 中选出的串的一个集合称为语言。如果 $\sum$ 是字母表，且 $L \subseteq \sum^{\ast}$，则 L 是 $\sum$ 上的语言
注意，$\sum$ 上的语言不必包含带有 $\sum$ 所有符号的串，所以，一旦确定 L 是 $\sum$ 上的语言，也就知道了 L 是任何是 $\sum$ 的超集的字母表上的语言
语言可看作串的集合，一个例子就是英语，合法英语单词全体就是包含所有字母的字母表上的串的集合
1.4 问题
在自动机理论中，一个问题就是判定一个给定的串是否属于某个具体语言的提问。
将要看到，任何在口头上称为 “问题” 的东西，竟然都可以表示成语言的成员性
更准确地说，如果 $\sum$ 是字母表，L 是 $\sum$ 上的语言，则问题 L 就是：
🔥 给定 $\sum^{\ast}$ 中的一个串 w，判定 w 是否属于 L
语言和问题其实相同。倾向于使用哪种术语依赖于所采取的观点。当只关心串本身时，如在集合 $\{0^n1^n \mid n\geqslant1 \}$，，就倾向于串的集合是语言。当给串赋予了“语义”，如认为串编码了图、逻辑表达式甚至偶数等。在这些情况下，对串所表示的东西的关心超过了对串本身的关心，就倾向于串的集合是问题
四. 确定性有穷自动机的定义
“确定型”是指这样的事实，在每个输入上存在且仅存在一个状态，自动机可以从当前状态转移到这个状态
一个确定型有穷自动机（DFA）包括：
- 一个有穷的状态集合，通常记作 Q
- 一个有穷的输入符号集合，通常记作 $\sum$
- 一个转移函数，以一个状态和输入符号作为变量，返回一个状态。转移函数通常记作 $\delta$ 。在非形式化表示自动机的图中，用状态之间的箭弧和箭弧上的标记来表示 $\delta$ 。如果 q 是一个状态，a 是一个输入符号，则 $\delta(q, a)$ 是这样的状态 p，使得从 q 到 p 有带 a 标记的箭弧。
- 一个初始状态 $q_0$，是 Q 中状态之一
- 一个接受状态的集合 F。集合 F 是 Q 的子集
可以用 $A=(Q, \sum, \delta, q_0, F)$ 这个 “五元组” 记号来表示 DFA，其中 A 是 DFA 的名字
4.1 DFA 如何处理串
关于 DFA 需要理解的第一件事情是，DFA 如何决定是否“接受”输入符号序列。DFA 的“语言”是这个 DFA 接受的所有串的集合
假设 $a_1a_2\dots a_n$ 是输入符号序列。让这个 DFA 从初始状态 $q_0$ 开始运行。查询转移函数 $\delta$ ，比如说 $\delta(q_0, a_1)=q_1$ ，以找出 DFA 在处理了第一个输入符号 $a_1$ 之后进入的状态。处理下一个输入符号 $a_2$ ，求 $\delta(q_1, a_2)$ 的值，假设这个状态是 $q_2$ 。以这种方式继续下去，找出状态 $q_3,q_4,\dots, q_n$ ，使得对每个 $i$，$\delta(q_{i-1} , a_i)=q_i$ 。如果 $q_n \in F$ ，则接受输入 $a_1a_2\dots a_n$，否则就“拒绝”
4.2 转移图
一个 DFA 的转移图是如下定义的图： (a) 对 Q 中每个状态存在一个顶点
(b) 对 Q 中每个状态 q 和 $\sum$ 中每个输入符号 a，设 $\delta(q, a)=p$ 。于是转移图有从顶点 q 到顶点 p 的带 a 标记的箭弧。如果有几个输入符号都导致从 q 到 p 的转移，则转移图有一个由这些符号列表标记的箭弧
(c) 有一个进入初始状态 $q_0$ 的带 Start 标记的箭弧。这个箭弧没有任何出发顶点
(d) 对应于接受状态（属于 F 的那些状态）的顶点用双圆圈标记。不属于 F 的状态用单圆圈
4.3 转移表
转移表是习惯上对像 $\delta$ 这样有两个变量和一个返回值的函数的表格表示。这个表的各行对应着状态，各列对应着输入。在状态 q 对应的行和输入 a 对应的列这个位置上的项是状态 $\delta(q,a)$
| 0 | 1 | |
|---|---|---|
| -> $q_0$ | $q_2$ | $q_0$ |
| * $q_1$ | $q_1$ | $q_1$ |
| $q_2$ | $q_2$ | $q_1$ |
4.4 课堂练习
- 设计一个 DFA，以接受语言 $L=\{w \mid w形如x01y，x和y是只包含0和1的两个串\}$
#include <stdio.h>
#include <string.h>
enum state
{
state_0,
state_1,
state_2,
};
bool isAcceptL(const char* str)
{
int cur_state = state_0;
for(int i = 0; i < strlen(str); ++i)
{
switch(cur_state)
{
case state_0:
if(str[i] == '0')
cur_state = state_1;
else if(str[i] == '1')
cur_state = state_0;
break;
case state_1:
if(str[i] == '0')
cur_state = state_1;
else if(str[i] == '1')
cur_state = state_2;
break;
case state_2:
if(str[i] == '0')
cur_state = state_2;
else if(str[i] == '1')
cur_state = state_2;
break;
}
}
if(cur_state == state_2)
return true;
else
return false;
}
int main(void)
{
const char* str = "11111111101";
printf("IsAccept: %d\n", isAcceptL(str));
return 0;
}
作业
-
设计一个 DFA，以接受语言 $L=\{ w \mid w 同时有偶数个 0 和偶数个 1 \}$
-
设计一个 DFA，以接受语言 $L=\{ w \mid w 形如 x00，x 是只包含0和1的串 \}$