Site Overlay

《形式语言与自动机》学习笔记 03-29 updated

第一章 基础知识

1.1 集合与关系

1.2 逻辑

1.3 图

1.4 证明技术

以上在《离散数学》已经学习过。略。

第二章 语言及文法

2.1 语言的定义与运算

字母表字符有限 集合。记作 $T$

字符串字符有限序列

字符串长度:字符串字符的个数。用绝对值符号表示。|asdf|=4

$a^n$ :表示 n 个 a 构成的字符串。

连接运算:把两个字符串排在一起,称为连接。例如 $\omega_1 = abc, \omega_2 = def$,则连接后 $\omega_1\omega_2=abcdef$.

空串:不包含字符的字符串,记作 $\varepsilon$.

*$T^$**:包含空串的该表上所有字符串的集合。

$T^+$:不包含空串的该表上所有字符串的集合。

语言(L)$T^*$ 的子集。

语言的积:语言的笛卡尔连接运算积。

语言的闭包:语言与自身的积所能产生的所有字符串。

*语言的 $L^$** 闭包:

$$
\begin{aligned}
\text { 设 } L &=\{b a, b b\}, \text { 则 } \\
L^{*} &=\{b a, b b\}^{*} \\
&=\{\varepsilon, b a, b b, b a b a, b a b b, b b b a, b b b b, \cdots\} \\
{L}^{+} &=\{b a, b b\}^{+} \\
&=\{b a, b b, b a b a, b a b b, b b b a, b b b b, \cdots\}
\end{aligned}
$$

2.2 文法

替代规则$\alpha \to \beta$,表示字符串 $\alpha$ 可被字符串 $\beta$ 代替。

终结符、非终结符:不能被任何字符代替的字符就是终结符,否则就是非终结符。

文法($G$): 文法是规定语言的产生规则的模型。通过四元组定义 $G=(N, T, P, S)$,其中:

(1) $N$ 非终结符的有限集合;
(2) $T$ 终结符的有限集合,且 $N \cap T=\varnothing$;也即字符表。
(3) $P$ 形式为 $\alpha \rightarrow \beta$生成式有限集合
(4) $S$ 起始符, 且 $S \in N$

一般用大写字母表示非终结符,小写字母表示终结符。

文法的字符集$(N \cup T )^*$

推导序列:文法 G 上有 $a_0,\cdots,a_n$,且 $a_i\Rightarrow a_{i+1}$,则 $a_0 \Rightarrow a_1\Rightarrow a_2\Rightarrow \cdots \Rightarrow a_n$ 是长度为 $n$ 的推导序列。

$\alpha \overset{*}{\underset{G}{\Rightarrow}} \alpha^{\prime}$:表示 $G$ 文法上,能通过长度大于等于 0 的推导序列,从 $\alpha$ 推出 $\alpha'$.

句型:若从起始符 S 能通过有限步推出字符串 $\alpha$ ,则 $\alpha$$G$ 的句型。

句子:若推出的句型 $\omega$ 属于终结符 $T^*$,则 $\omega$ 称为一个句子。

文法产生的语言 $L(G)$:若文法推导出的所有句型构成了一个集合,那么这个集合是该文法产生的语言,记作 $L(G)$.

2.3 文法的分类

Chomsky 文法体系分类

类型 要求 例子
0型 (无限制文法) 图灵机
1型 (上下文有关文法) 生成式: $\alpha \rightarrow \beta, \quad \alpha \leq \mid\beta \mid$ 线性有界自动机
2型 $($ 上下文无关文法) $\mathrm{A} \rightarrow \alpha, \quad \mathrm{A} \in \mathrm{N}, \quad \alpha \in(\mathrm{N} \cup \mathrm{T})^{*}$ 下推自动机
3型 (正则文法/线性文法) 右线性文法: $\mathrm{A} \rightarrow \omega \mathrm{B} \mid \omega, \quad \mathrm{A}, \mathrm{B} \in \mathrm{N}, \quad \omega \in \mathrm{T}^{*}$
左线性文法: $\mathrm{A} \rightarrow \mathrm{B} \omega \mid \omega, \quad \mathrm{A}, \mathrm{B} \in \mathrm{N}, \quad \omega \in \mathrm{T}^{*}$
有限自动机

1 型文法:每个生成式的源字符串小于等于产生的字符串

2 型文法:每个生成式的源字符串都是 单个非终结符

3 型文法:右线性文法就是就是推导出来的字符串右侧以非终结符结尾。

上下文有关语言 :由上下文有关文法产生的语言称为上下文有关语言;

上下文无关语言 :由上下文无关文法产生的语言称为上下文无关语言;

正则语言 :由正则文法产生的语言称为正则语言;

无限制性语言 :由 0 型文法产生的语言则称为无限制性语言。

2 型文法的表示法

巴克斯范式(BNF,Backus Normal Form)

c.f. 语法格式描述规范BNF、EBNF、ABNF - 简书 (jianshu.com)

::=` :是“被定义为”的意思;示例:`字符串 ::= 用引号包围的字符序列`,表示 `字符串` 就是 `用引号包围的字符序列

"...":终结符,即引号中的字符序列本身,并非指代其它字。而终结符双引号 "double_quote 用来表示;示例:函数调用 ::= 名字 "()" 表示 函数的调用 是 由 名字 加上左右括号字符 () 组成;

double_quote :代表终结符 双引号 "; 示例:字符串 ::= double_quote ... double_quote,表示 字符串 是由被字符 " 包围的字符序列组成;

在双引号外的字代表着语法部分;示例:基本类型 ::= 字符串 | 数字 | 布尔,表示 字符串数字布尔 都是 基本类型,但 字符串数字布尔 具体是什么,由其它 规则定义;

<...>:必选项;示例:名字 ::= [姓] <名> 表示 名字 中的 是必须要有的,但 是可有可无的,即:姓 名名字 也是 名字

[...]:可选,可有可无;示例:名字 ::= [姓] <名> 表示 名字 中的 是必须要有的,但 是可有可无的,即:姓 名名字 也是 名字

{...}`:重复,0 或 任意次重复;示例:`AB ::= "a" {"b"}`,表示 `AB` 是由 一个 `a` 后面跟上任意数量(包括0个)个 `b` 组成,如 `a`、`a b`、`a bb`、`a bbb

(...):分组,用来控制表达式的优先级;示例:AX ::= "a" ("m"|"n"),表示 AX 是由 一个 a 后面跟上 mn 组成;

|:替换,即 的意思;示例:布尔 ::= "true" | "false",表示 truefalse 都是 布尔

...:表示各种列举或省略的代码片断;示例:a...z 表示 从 az 的字符,"..." 表示 由 双引号 " 包围起来的任意字符;

语法图

第三章 有限自动机和右线性文法

3.1 有限自动机

有限自动机所定义的语言属于 3 型语言

有限状态系统:状态有限、离散

连续状态系统:状态无限、连续

有限自动机的组成

有限自动机 = 控制器 + 字符输入带 + 控制器当前读取位置。

其中控制器包括有限个状态状态的转换关系,状态的转换可以与输入有关。

DFA:有限自动机每次转换的 后继状态唯一,则是确定有限自动机。

NFA:有限自动机每次转换的 后继状态唯一,则是不确定有限自动机。

状态转换图

  • 起始状态:用空箭头的指向表示。

  • 读入字符:用箭头上的字符表示。

  • 终止状态:用双圈表示。

有限自动机的形式定义

DFA 是五元组 $M=(Q,T,\delta,q_0,F)$。其中:

  • Q:状态表。(有限)
  • T:输入字母表。(有限)
  • $\delta$:转换函数。$\delta: Q\times T\to Q$.
  • $q_0$ 初始状态。属于 Q。
  • F:终止状态表。包含于 Q。

$\delta$ 是针对 字符输入 的转换函数。

$\delta'$ 用于表示 字符串输入 的转换函数。

$\delta^{\prime}$ 的定义如下:

  • $\varepsilon \in T^{*},$$\delta^{\prime}(q, \varepsilon)=q$;
  • 对任意 $a \in T$$\omega \in T^{*}$, 有 $\delta^{\prime}(q, \omega a)=\delta\left(\delta^{\prime}(q, \omega), a\right)_{\circ}$

$\delta^{\prime}(q, \varepsilon)=q$ 表明:若无字符输入,状态不变

$\delta^{\prime}(q, \omega a)=\delta\left(\delta^{\prime}(q, \omega), a\right)$ 表示:读取字符串相当于:先字符串中第 1 个字符,再在新状态的基础上读取第 2 个字符,也即可分解。

被接受 如果有 $\delta^{\prime}\left(q_{0}, \omega\right)=p, p \in F,$ 那么称字符串 $\omega$ 被有限自动机 $M$ 所接受

被状态机接受的语言$L(M)$ 则表示 $M$ 所接受的语言,表示为

$$
L(M)=\left\{\omega \mid \delta^{\prime}\left(q_{0}, \omega\right) \in F\right\}
$$

格局:描述状态机的工作现场的二元组,用 $(q,\omega)$表示,其中 $\omega$ 表示当前等待输入的字符串,$q$ 表示当前状态。

初始格局、终止格局:在初始状态和终止状态的格局。

格局转换$(q, a \omega) \vdash \left(q_{1}, \omega\right)$$\vdash $ 作为连接符。

被确定状态机接受的字符串:某个字符串在初始状态输入,能够达到最终状态。$(q_0, \omega) \vdash \left(q_{f}, \varepsilon\right)$

3.2 不确定的有限自动机(NFA)

NFA:若对于同样的输入,此状态可能走向不同的下一状态,则此状态机是 NFA.

被 NFA 接受:若对于输入串,存在一种过程使得能走到终止状态,则此输入串被接受。

DFA 是五元组 $M=(Q,T,\delta,q_0,F)$。其中:

  • Q:状态表。(有限)
  • T:输入字母表。(有限)
  • $\delta$:转换函数。$\delta: Q\times T\to \mathcal {P}(Q)$.(与 DFA 的唯一区别
  • $q_0$ 初始状态。属于 Q。
  • F:终止状态表。包含于 Q。

对字符串输入的转换函数

  1. $\varepsilon \in T^{*},$$\delta^{\prime}(q, \varepsilon)=\{q\}$;
  2. 对任意 $a \in T, \omega \in T^{*},$$\delta^{\prime}(q, \omega a)=\left\{p \mid\right. \text { 存在 } {r} \in \delta^{\prime}({q}, {\omega}) \wedge {p} \in \delta({r}, {a})\}; $ (此处的含义:状态转移后能到达的状态,是对应每个状态接受字符 $a$ 后的能达到的状态集合的并集)
  3. $\delta^{\prime}(P, \omega)=\bigcup_{q \in P} \delta^{\prime}(q, \omega), P \subseteq Q_{\circ}$

NFA 可接受的语言$L(M)=\left\{\omega \mid \delta^{\prime}\left(q_{0}, \omega\right)\right.$$F$ 中的一个状态 $\}$ (含义:能从头走到终止状态)

3.3 NFA 和 DFA 的等价性

NFA 便于设计,DFA 便于实现。实际上两种状态机能识别相同的语言类(此为等价的定义)。

完善的证明的过程略,可以这样理解:

  1. DFA 是 NFA 的特例。
  2. NFA 可以通过增加状态的 DFA 实现(例如 KMP 算法,在数电中的设计,序列检测器,我们通过状态来保存接收到的序列。)
  3. 因此两者等价。

找出给定状态机的等效状态机的方法

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注