Finite Automata
确定型有穷自动机
Deterministic Finite Automata, DFA
形式化定义
自动机是一个5元组
- ：状态集 (states)
- ：字母表 (alphabet)
- ：转移函数 (transition function)
- ：起始状态（start state）
- ：接受状态集（ (accept states)
当自动机接收到输入字符串，它处理这个字符串并产生一个输出（接受或拒绝）。
- 若 是机器 接受的全部字符串集，则称 是 的语言，记作 ，又称 识别 (Recognize) 。例，以1结束
- 如果机器不接受任何字符串，它仍然识别空语言
- Exactly one transition per input per state: A DFA can take only one path through the state graph.
非确定型有穷自动机
Nondeterministic Finite Automata, NFA
相关概念
- 非确定性是确定性的推广，因此每一台确定型有穷自动机也是一台非确定型有穷自动机，非确定型有穷自动机可能有一些另外的特征。
- DFA 的每一个状态都必须有 中每一个字母的对应箭头去向； NFA 的每一个状态对于 中每一个符号可能有 0 个、1 个或多个射出的箭头。(NFA Can have zero, one, or multiple transitions for one input in a given state.)
- DFA 转移箭头上的标号只能取自字母表的符号，而 NFA 的来自字母表的符号或 。(NFA Can have ε-moves.Machine can move from state move from state A to state state B without reading input.)
- Epsilon: (Not the empty set, but set with a single, empty, string.)
- 可以把非确定性看作是若干独立的“过程”。
- 在计算过程中，机器可以在多种可能性动作中选择一种继续进行。机器把自己复制成多个备份，并行执行所有的可能性。
- 如果计算的某个分支导致接受状态，则机器接受该输入。
- NFA 与 DFA 具有等价性
- 每一台 NFA 都可以转换成一台等价的 DFA，构造 NFA 有时比构造 DFA 容易。
形式化定义
广义非确定型有穷自动机
A Generalized Nondeterministic Finite Automaton (GNFA) is similar to an NFA, but allows regular expressions as transition labels.
要求 GNFA 具有下述条件的特殊形式：
- 接受状态和起始状态不同。
- 起始状态有射出到其他每一个状态的箭头，但是没有射入到其他任何状态的箭头。
- 有唯一的一个接受状态，它从其他每一个状态有射入的箭头，但是没有射出到任何其他状态的箭头。
- 除起始状态和接受状态外，每一个状态到自身和其他每一个状态都有一个箭头。
正则语言
与有穷自动机有等价性
- 正则表达式
- ：由 0 个或多个 中的串连接构成所有串
- ：由 1 个或多个 中的串连接构成所有串
- 正则运算符
- 连接 (Concatenation)：
- 并 (Union)：
如果 是正则语言，那么 和 也是正则语言。
- Option: (零个或一个)
- Range:
Example: The set of all strings that do not contain the substring 00.
(01)*
(10)*
(11)* → 1*
泵引理
Pumping Lemma
只能用来反证某个语言不是正则语言
要证明某个语言是正则语言，则应构造出相应的 DFA 或 NFA
是一个正则语言，则存在数字 （pump length，泵长度）使得，如果 是语言中任一长度不小于 的字符串，那么 可以被分为3段，，满足下述条件：
- ，对于每一个
即正则语言中的字符串包括一段子串，把该子串重复任意次，得到的字符串仍在语言中。
例子
构造 NFA
构造 DFA
可能不止一个接受状态，可能接受状态还有转移箭头射出
{w| w has at least three a’s and at least two b’s}
The state diagram of that recognizes ={w| w has at least three a’s}:
The state diagram of that recognizes ={w| w has at least two b’s}:
Therefore, the state diagram of that recognizes ={w| w has at least three a’s and at least two b’s}：
任意挑一条路走到终点
一定会经过五个状态
终点再无限循环 a, b 即可
{w| w has exactly two a’s and at least two b’s}
The state diagram of that recognizes ={w| w has exactly two a’s}:
不接受超过两个b后的输入
陷入循环状态，无法终止
The state diagram of that recognizes ={w| w has at least two b’s}:
Therefore, the state diagram of that recognizes ={w| w has exactly two a’s and at least two b’s}:
{w| w has an even number of a’s and one or two b’s}
The state diagram of that recognizes ={w| w has an even number of a’s}:
0 个 a 也属于偶数，一开始就可以进入接受状态
The state diagram of that recognizes ={w| w has one or two b’s}:
两个终止状态
Therefore, the state diagram of that recognizes ={w| w has an even number of a’s and one or two b’s}:
{w| w has an odd number of a’s and ends with b}
The state diagram of that recognizes ={w| w has an odd number of a’s}:
The state diagram of that recognizes ={w| w ends with b}:
Therefore, the state diagram of that recognizes ={w| w has an odd number of a’s and ends with b}:
起始状态射出的两个箭头
即字符串开头是 a 或 b 的两种情况（路线）
{w| every odd position of w is a 1}
有陷阱，可以接受空字符串。
Think of the problem statement as an implication. If is an odd position, then is 1.
{w| w is any string not in a*b*}
DFA that recognizes = {w| w is any string in a*b*} as follows
a*b* 包括空集则一开始就可以接受
Therefore, DFA that recognizes {w| w is any string not in a*b*} as follows:
转换 NFA 为 DFA
答案
- 确定等价DFA 的所有状态
- 有3个状态，所以 有8个状态。每一个状态对应 的一个状态子集，于是 的状态集为
- 确定 的起始状态和接受状态
- 起始状态
- 它等于从1出发沿着 (空串)箭头能够到达的所有状态加上1本身
- 接受状态
- 的接受状态 以及它的子集
- 确定 的转移函数
DFA不考虑输入 没有意义
(有 箭头，可以转回来)
… 以此类推
或者画表格
ㅤ | a | b |
1 | ∅ | 2 |
2 | 2,3 | 3 |
3 | 1,3 | ∅ |
1,2 | 2,3 | 2,3 |
1,3 | 1,3 | 2 |
2,3 | 1,2,3 | 3 |
1,2,3 | 1,2,3 | 2,3 |
- 删掉不可达的状态后得到与等价的DFA
- {1} 和 {1,2} 属于没有箭头射入的状态
构造正则表达式
答案
化简最终目标：
一个起始状态S 直接到一个接受状态 F
消除状态1，改为到达状态2的两种方式
答案
证明非正则语言
记得横跨两种字母的情况
证明 不是正则语言。
假设是正则的。令是由泵引理给出的泵长度，。
因为是的子字符串且长度大于，所以泵引理保证可以分成3段，使得对于任意的，在中。下面考虑3种情况，说明这个结论是不可能的。
- 字符串只包含0。字符串中0比1多，从而不是的成员，矛盾。
- 字符串只包含1。同理矛盾。
- 字符串既包含0也包含1。这种情况下，字符串中0和1的个数可能相等，但它们的顺序乱了，在0的前面出现1。因此，不是的成员，矛盾。
证明 不是正则语言。
已知是非正则的。
假设是正则的，则也是正则的。
但产生矛盾，则是非正则的。
证明 不是正则语言。
假设是正则的，则存在
…
选择 没有意义：
无论怎么分割， 只包含一堆 0，永远对称（），则属于 F，无法产生矛盾。