例2
请设计 DFA, 在任何由 0 和 1 构成的串中, 接受含有 01 子串的全部串

{0，1}的子串全部串有：0，1，01，故本题有三种状态

1. 未发现 01, 即 0 没有出现过;
2. 未发现 01, 但刚刚读入字符是 0;
3. 已经发现了 01.
   因此 DFA A 可定义为：A = ({q1,q2,q3},{0,1},δ,q1,{q3})
   其中 δ 为:
   δ(q1,1) = q1 δ(q2,1) = q3 δ(q3,1) = q3
   δ(q1,0) = q2 δ(q2,0) = q2 δ(q3,0) = q3

将此DFA用状态转移图表示：其中q1为初始状态

将此DFA用状态转移表表示：

求解接受全部含有 01 子串的 DFA, ˆ δ 处理串 0101 的过程
解题过程借助如上的状态转移图

注意：ˆ δ(q0,ε) = δ(q0,0)

例3.
若 Σ = {0,1}, 给出接受全部含有奇数个 1 的串 DFA
状态有两个：q0→偶数个1，q1→奇数个1，其中q1为接受状态

例4.
若 Σ = {0,1}, 给出接受全部含有偶数个 0 和偶数个 1 的串 DFA
接受状态：00，11，1100，111100，…

例5.
对任何状态 q 及字符串 x 和 y, 证明 ˆ δ(q,xy) = ˆ δ(ˆ δ(q,x),y)
@注意，类似此类证明，均对y进行数学归纳法
1.y = ε 时,i

例7.
由 0 和 1 构成的串中, 接受全部以 01 结尾的串, 如何设计 DFA?
q0: XX11
q1:XXX0
q2:XX01


续例7. 接受全部以 01 结尾的串的 NFA.

五元组为 A = ({q0,q1,q2},{0,1},δ,q0,{q2}),
转移函数 δ:
δ(q0,0) = {q0,q1} δ(q1,0) = ∅ δ(q2,0) = ∅
δ(q0,1) = {q0} δ(q1,1) = {q2} δ(q2,1) = ∅

续例7.
接受 01 结尾的串的 NFA, ˆ δ 处理 00101 时每步的状态转

1. ˆ δ(q0,ε)={q0}
2. ˆ δ(q0,0) = δ(q0,0) = {q0,q1}
3. ˆ δ(q0,00) = δ(q0,0)∪δ(q1,0) = {q0,q1}∪∅ = {q0,q1}
4. ˆ δ(q0,001) = δ(q0,1)∪δ(q1,1) = {q0}∪{q2} = {q0,q2}
5. ˆ δ(q0,0010) = δ(q0,0)∪δ(q2,0) = {q0,q1}∪∅ = {q0,q1}
6. ˆ δ(q0,00101) = δ(q0,1)∪δ(q1,1) = {q0}∪{q2} = {q0,q2}

因为 q2 是接受状态, 所以 NFA 接受 00101

例8.
设计 L = {w ∈{0,1}∗ | w 的首尾字符相同.} 的 NFA

续例11.
L = {w ∈{0,1}∗ | w 倒数 3 个字符至少有一个是 1} 的 NFA.

例4.

例5.
给出正则表达式 (aa)∗(bb)∗b 定义的语言

例6.
Design regular expression for L = {w | w consists of 0’s and 1’s, and the third symbol from the right end is 1.}

(0+1)∗1(0+1)(0+1)

例7.
Design regular expression for L = {w | w ∈{0,1}∗ and w has no pair of consecutive 0’s.}

例9.
将如图 DFA 转换为正则表达式.


例10.
利用状态消除法, 设计下图自动机的正则表达式.



例11.
正则表达式 (0+1)∗1(0+1) 构造为 ε-NFA

例12. 判断 (L + M)∗ = (L∗M∗)∗.

1. 将 L 和 M 替换为 a 和 b;
2. (a+b)∗ ?= (a∗b∗)∗;
3. 因为 L((a+b)∗) = L((a∗b∗)∗);
4. 所以 (L + M)∗ = (L∗M∗)∗.

例16.
若语言 L = (00+1)∗, 同态 h : {a,b}→{0,1}∗
为h(a) = 01, h(b) = 10,
请证明 h−1(L) = (ba)∗

1. 若w以a开头，则h(w) starts with 01,h(w) not in L;
2. if w ends with b, then h(w) end with 10, h(w) not in L;
3. if w contains consecutive aa, then h(w) contains 0101, h(w) not in L;
4. if w contains consecutive bb, then h(w) contains 1010, h(w) not in L;
   So, h-1(L)=(ba)*

例17.
For a language L, define head(L) to be the set of all prefixes of strings in L. Prove that if L is regular, so is head(L)

1.形式语言

（1）语言

• 语言可以了解为一个抽象的数学系统，是按照一定的规律构成的句子和符号串的有限或无限的集合
• ==语言描述的三种途径 ==
  （1）穷举法：只适合句子数目有限的语言
  （2）语法描述：生成语言中合格的句子
  （3）自动机：对输入的句子进行检验，区别哪些是语言中的句子，哪些不是语言中的句子

（2）形式语言

形式语言

• 直观意义（定义）：形式语言是用来精确地描述语言（包括人工语言和自然语言）及其结构的手段。
• 形式语言学，也称为代数语言学。
• 形式语言以重写规则 α→β的形式表示，其中α与β均为字符串。一个初步的字符串通过不同的顺序，不断应用不同的重写规则，可以得到不同的新字符串。

形式语法

形式语法是一个4元组G=(N,sigma,P,S)。
其中N为非终结符的有限集合，或者说叫做变量集或语法种类集；
sigma是终结符的有限集合，且有N∩sigma=∅；
V=N∪sigma称为总词汇表；
P是一组重写规则的有限集合：P={α→β}，其中均为V中元素构成的字符串，且α中至少应该含有一个非终结符号；
S∈N，称为句子符或者初始符。

举个栗子：

关于推导

（1）推导的定义

传递闭包：

自反和传递闭包：

当确定或者默认某个推导是由文法G所产生的，则推导符号下方的G可以省略不写。

（2）最左推导、最右（规范）推导
最左推导：约定每步推导中只改写最左边的那个非终结符。
最右推导（规范推导）：约定每步推导只改写最右边的那个非终结符。

一个栗子：

（3）关于句型与句子

文法G的不含非终结符的句子形式成为G生成的句子。
由文法G生成的语言，记做L（G），指G生成的所有句子的集合，即有
L （ G ） = { x ∣ x ∈ ∑ , S ⇒ ∗ x } L（G）=\{x|x\in \sum,S \overset{*}\Rightarrow x \} L（G）={x∣x∈∑,S⇒∗x}

（4）关于正则文法（3型文法）
左线性正则文法称为3型文法
关于正则文法，如果文法G=（N,sigma，P，S）的P，其中的规则满足如下的形式：A→Bx，或A→x，其中A，B∈N，x∈sigma，则称该文法为正则文法或3型文法（左线性正则文法）；
满足A→xB，则称该文法为右线性正则文法。

（5）上下文无关文法（2型文法）——上下文有关文法的特例
context-free grammar（CFG）
如果P中的规则满足如下形式：A→α，其中A属于N，α属于（N∪sigma）*，则称该文法为上下文无关文法，或称2型文法。

一个栗子：

（6）上下文有关文法（1型文法）
context-sensitive grammar，CSG
如果P中的规则满足如下形式：αAβ→αγβ，其中A∈N，α，β，γ∈（N∪sigma）*，且γ中至少包含一个字符（A直接消去的情况不予记录），则称该文法为上下文有关文法，或1型文法。

当α和β均为空时，上下文有关文法转化为上下文无关文法，无关文法是有关文法的特例。

或者定义为如下形式：

一个栗子：

（7）无约束文法（0型文法、无限制重写系统）
如果P中的规则满足如下形式：α→β，α，β是字符串，则称G为无约束文法，或称为0型文法。

如果一种语言能由几种文法产生，则把这种语言称为在这几种文法中受限制最多的那种文法所产生的的语言。

（8）上下文无关文法产生的语言句子的派生树表示的步骤：
CFG
G = (N,sigma，P,S)

1. 对于任意x∈N∪sigma，给一个标记作为节点，S作为树的根节点。
2. 如果一个节点的标记为A，并且它至少有一个除他自身之外的后裔，则A∈N。
3. 如果一个节点的标记为A，它的k（k>0）个直接后裔节点按照从左到右的次序一次标记为A1，A2,A3……Ak，则有A→A1A2……Ak一定是P中的一个产生式。

派生树又称语法树、分析树、推导树
一个栗子：

（9）上下文无关文法的二义性
一个文法G，如果存在某个句子有不只一棵分析树与之对应，则称这个文法是二义的。

2. 有限自动机与正则文法

（1）确定的有限自动机

（2）不确定的有限自动机

（3）确定的有限自动机和不确定的有限自动机的区别

（4）确定的有限自动机和不确定的有限自动机的关系

（5）正则文法与有限自动机的关系

3 有限自动机在NLP中的应用

（1）在NLP中，英语单词的拼写检查：
设X为拼写错误的字符串，长度为m，Y为X对应的GT，长度为n。则X与Y 的编辑距离ed(X[m],Y[n])定义为：
从字符串X转换到Y所需要的插入、删除、替换和交换两个相邻的基本单位字符的最小个数。

（2）对于有限状态机
构造一个确定的有限状态机R，有定义R=(Q,A,δ,q0,F)
其中Q表示状态集，A表示输入字符集，δ为QxA→Q的一个函数，q0∈Q，为起始状态，F包含于Q为终止状态集。

当L包含于A*表示有限状态机R接收的语言，字母构成的所有合法单词都是有限状态机中的一条路径。当给定一个输入 串，对其进行检查的过程就是在给定阈值t（>0）的情况下，寻找那些与输入串的编辑距离小于t的路径。则一个字符串X[m]∉L能够被R识别的条件是存在一个非空集合C：

即存在一条L中存在的已知路径，该路径与X间的路径距离不大于t

（3）单词拼写检查
一般，英文单词可以使用键树（数字查找树）来存储。


关于为何使用t作为变量，编辑距离中X长度的取值范围：
若X的长度小于n-t，则X需要至少t+1次的增加操作才能达到与字符串Y相同；
若X的长度大于n+t，则X至少需要t+1次的删除操作才能达到与字符串Y相同。

仔细观察上图，关于阈值t，并非X与Y长度差的二分之一，而是我们前文中提到的，事先设定的阈值

由此有了上图右下角的说明：
关于阈值t的作用：是为了确定截取X的范围；进一步地，也能限制编辑距离（有可能小于阈值长度t）。

一个栗子：

（4）关于采用深度优先搜索算法从自动机中选择路径：



（5）关于使用有限自动机进行英语单词形态分析

Note：在实际的应用中，除了有限状态机，还常常使用有限状态转换机（Finite State Transducer，FST）的概念。
粗略的讲，有限状态转换机与有限自动机（有限状态机）的区别：
有限状态转换机FST在完成状态转移的同时产生一个输出。而有限自动机FA或有限状态机FSM只实现状态的转移，而不产生任何输出。

可以观察到，在上述的状态转换过程中，有限状态转换机在状态转移的过程中，还产生了字符的输出。

4 课后习题

（a）

(b)

$$L(G)=a^{t+1}\cdot b^{t+1}\cdot c^{t+1}$$

哈尔滨工业大学2019年《形式语言与自动机》期末试题

1. Design a DFA for the language L = {w∈{0,1}* | w contains both 01 and 10 as substrings}.

2. Design a NFA within four states for the language {a}*∪{ab}*.

3. Design regular expressions for language over Σ = {0,1}.
   (1).All strings contain the substring 001.
   (2).All strings expect the string 001.

4. Prove that L = {0^m1ⁿ | m/n is an integer} is not regular with pumping lemma.

5. Convert the following NFA into DFA with subset construction.
   

6. Give a context-free grammar for L = { aⁱb^jc^i+j|i,j>=0}

7. Let L be the language generated by the grammar G below
   S->AB|BBB
   A->Bb|ε
   B->aB|A
   (1).消除空产生式
   (2).消除单元产生式
   (3).转换到CNF

8. Design a PDA for L = {w∈{a,b}*|w has more a’s than b’s}

9. Prove : for every context free language L, the language L’ = {0^|w||w∈L} is also context free.

10. Design a Turing Machine that computes the following function f:0ⁿ->Binary(n)
    Where integer n>=1 and binary(n) is the binary representation of n.
    For example: f(0³) = 11 f(0⁵) = 101.

注：此题目为考试试卷实录，敬请放心食用。