形式语言与自动机学习笔记(2)：正则语言与有限自动机

有限自动机

DFA

DFA是一个五元组$M = (Q,T,\delta. q_0, F)$；

• $Q$：有限状态集合；
• $T$：有限的输入字母表；
• $\delta$：转移函数：$Q \times T \rightarrow Q$；
• $q_0$：起始状态；
• $F$：终止状态的集合；

$\delta'$函数：接受一个字符串输入的状态转移函数：

$$\delta':Q\times T^* \rightarrow Q$$

对任何$q \in Q$，作出如下定义：

• $\delta'(q, \varepsilon) = q$；
• 若$\omega$为字符串，$a$为一个字符，则$\delta'(q, a\omega) = \delta(\delta'(q, \omega), a)$；

被DFA接受的字符串：输入结束后使DFA达到终止状态；

格局：当前状态$q$，待输入字符串$\omega$，用$(q, \omega)$表示当前瞬时状态；

NFA 不确定的有限自动机

在某个状态，对应某个输入，有多个转移，能到达多个状态；NFA和DFA的定义上的区别只有$\delta$函数：

$$\delta：Q\times T\rightarrow 2^Q$$

如果接受一个字符串后NFA能够到达的状态集合包含一个及以上F中的元素，则称为该字符串能被NFA接受；

正则集和正则式

• 正则集：字母表上一些特殊形式的字符串的集合，是正则式说表示的集合；
• 正则式：用类似代数表达式的方式表示正则语言；
• 运算：（按照运算优先级从高到低排序）
  • $*$(closure)闭包；
  • $\cdot$ (concatenation)连接；
  • $+$ (union)联合

注：

• 正则式相等等价于正则集相等；
• 一个正则式对应一个正则集，但一个正则集可能有多个正确的正则式；

右线性文法与正则式

右限性文法又称正则文法。右线性文法和正则式都可以用代表正则语言；

从右线性文法导出正则式

设$x \rightarrow \alpha x + \beta(\Leftrightarrow x \rightarrow \alpha x 和x\rightarrow \beta)$，其中$\alpha \in T^*,\beta \in (N + T)^*,x\in N$，则：$x$的解为$x = \alpha^*\beta$；

正则集与右线性文法

• 正则集是由右线性文法产生的语言；
• 右线性文法产生的语言都是正则集；
• 一个语言是正则集，当且仅当该语言问右线性语言；

正则式与有限自动机

从DFA构造等价的正则表达式

状态消去法

具体步骤：

从正则式构造等价的$\epsilon$-NFA

归纳构造法

右线性语言与有限自动机

定理：由任意右线性文法定义G定义的语言必然能被一个NFAM所接受，即$L(G) = L(M)$；

构造与右线性文法等价的NFA

省流：

1. 新增一个状态作为终止状态；
2. 对仍在扩展非终结符的生成式，则转移到对应状态；
3. 对到达终结符的生成式，则转移到新增的结束状态；
4. 结束状态不存在转移；

构造能接受NFAM定义的语言的有限性文法

DFA的极小化

填表法；

Pumping定理

判定正则语言的必要条件；
定理：设$L$是正则集，存在常数$n$，对字符串$\omega \in L$且$\left | \omega \right | > n$，则$\omega$可以写成$\omega_1\omega_o\omega_2$，其中$\left | \omega_1 \omega_0\right | \le n$，$\left | \omega_0\right | > 0$，对所有的$i \ge 0$，有$\omega_1\omega_0^i\omega_2 \in L$；

显然，该定理可以用来证明某个语言不是正则语言；

证明步骤：

1. 对于足够大的n；
2. 找到一个满足以下条件的串$\omega \in L$（串长至少为n）；
3. 任选满足$\omega = \omega_1\omega_o\omega_2$，其中$\left | \omega_1 \omega_0\right | \le n$，$\left | \omega_0\right | > 0$；
4. 找到一个$i$，使得$\omega_1\omega_0^i\omega_2 \notin L$；