形式语言与自动机 Part.4 正则语言，2DFA，Mealy&Moore机

课程名：形式语言与自动机

作者：Lupinus_Linn

许可证：CC-BY-NC-SA 3.0 创作共用-署名-非商业性-相同方式共享

• 署名（英语：Attribution，BY）：您（用户）可以复制、发行、展览、表演、放映、广播或通过信息网络传播本作品；您必须按照作者或者许可人指定的方式对作品进行署名。
• 非商业性使用（英语：Noncommercial，NC）：您可以自由复制、散布、展示及演出本作品；您不得为商业目的而使用本作品。
• 相同方式共享（英语：Sharealike，SA）：您可以自由复制、散布、展示及演出本作品；若您改变、转变或更改本作品，仅在遵守与本作品相同的许可条款下，您才能散布由本作品产生的派生作品。（参见copyleft。）

引用：

• 本文中部分文字与图片引用自北京邮电大学计算机学院王柏教授的《形式语言与自动机》课程课件。
• 绪论中的证明方法部分引自清华大学王生原老师课件。
• 部分题目插图引用自北京邮电大学出版社《形式语言与自动机 第二版》教材。

在此一并表示感谢，并不做商业用途。

本笔记所有内容的传送门

Part.1绪论, Part.2 语言与文法
Part 3.有限自动机
Part.4 正则语言，2DFA，Mealy&Moore机
Part.5 上下文无关语言与下推自动机(PDA)
Part.6 图灵机

Part.4 正则语言

4.1 基本概念

• 正则语言：满足正则语言的判定定理的语言。
• 正则(表达)式：用类似代数表达式的方法表示正则语言。
• 正则式的相等：表示的语言相同。
• 正则集：满足正则式的字符串的集合。
• 正则式和语言的的联合运算+，连接运算•，正闭包$L^+$L+，星闭包$L^*$L∗及运算性质。

注1：正则集是T* 的子集。(即正则集是T*上的语言)
注2：L+包含ε当且仅当L包含ε。
注3：每个正则集至少对应一个正则式（可有无穷多 个正则式）

4.2 右线性文法↔正则表达式

两个等价

1. 左线性文法和右线性文法等价。
2. 右线性文法和正则式等价（右线性文法产生的语言都是正则语言，正则语言都可以用右线性文法产生）
   从右线性文法导出正则式：设$x\rarr \alpha x+\beta,\alpha \in T^*,x\in N,then\ x=\alpha^*\beta$x→αx+β,α∈T∗,x∈N,then x=α∗β。不断代入消元，最后得出$S= <RE>$S=<RE>

4.3 正则语言可以表示为有限自动机、正则表达式和右线性文法

三者两两等价，都表示正则语言

例子：

G=（{S，A}，{0，1}，P ，S）其中P：S—>1A，A—> 0A |1S|0

1. 文法转正则式：解方程
   $A\to 0A|1S|0,即A\to 0A|11A|0，解得A=(0+11)^*0，得S=1(0+11)^*0$A→0A∣1S∣0,即A→0A∣11A∣0，解得A=(0+11)∗0，得S=1(0+11)∗0

2. 正则式转文法：按照运算顺序，按基本运算还原。
   $1,(0+11)^*,0$1,(0+11)∗,0是依次连接的，对应文法的连接，则$S\to 1A0,A\to (0+11)^*$S→1A0,A→(0+11)∗
   闭包运算的文法是$A\to aA|\epsilon$A→aA∣ϵ，所以$A\to 0A|11A|\epsilon$A→0A∣11A∣ϵ

3. 文法转自动机：生成一个吃一个，生成终结符串的，转移到一个新增的接受状态。
   因为mermaid语法的限制，用方形框表示接受。
   $S\to 1A$S→1A，则状态$q_S$qS​用字符$1$1转移到状态$q_A$qA​，其他以此类推。
   $A$A可以推出终结符串$0$0，则$q_A$qA​通过$0$0转移到新的接受状态$q_H$qH​

4. 自动机转文法：每一个转移，对应一个产生式。转移到接受状态的，额外增加推出终结符串。
   $q_S$qS​接受$1$1转移到$q_A$qA​，所以文法有产生式$q_S\to 1q_A$qS​→1qA​，其他以此类推。
   最后可能要做三消（消单消空消递归）。
   $q_S\to 1q_A\\ q_A\to 1q_S\\ q_A\to 0q_A\\ q_A\to \bold{0q_H|0}$qS​→1qA​qA​→1qS​qA​→0qA​qA​→0qH​∣0

5. 自动机转正则式：状态消去法
   要消去状态$q_A$qA​，入射$q_A$qA​的有$\{q_S\}${qS​}，出射$q_A$qA​的有$\{q_H,q_S\}${qH​,qS​}，所以对$q_S$qS​到$q_H$qH​，$q_S$qS​到$q_S $有影响。

   此时已经是基本结构，一举写出
   $S=(10^*1)^*10^*0$S=(10∗1)∗10∗0

6. 正则式转自动机：按照运算顺序，按基本运算还原。
   用$S=1(0+11)^*0$S=1(0+11)∗0来还原，5.里那个比较复杂。
   $1,(0+11)^*,0$1,(0+11)∗,0是依次连接的，对应自动机某一些状态区域的空转移。
   空闭包的结构是，要么空转移，要么在原地转圈后转移。
   0+11的结构是，两条并行线。
   11结构是，顺序执行。

4.4 有限自动机→正则表达式：状态消去法

精髓：将正则表达式作为转移弧的标记。不断删去状态，删去状态时将其前驱和后继的转移弧标记修改。删到基本结构时写出最终表达式。

删除方法：

基本结构：

对于$q\in F$q∈F

1. $q\ne q_0$q​=q0​，则正则表达式为$(R+SU^*T)^*SU^*$(R+SU∗T)∗SU∗，即观察从$q_0$q0​到$q$q的可能路径。
   为到达$q_0$q0​，可以在$q_0$q0​自环转任意次或者$q_0$q0​和$q$q之间反复横跳任意次。
   之后要到达$q$q，一定会单独经过一次$S$S，然后在$q$q又可以自环转任意次。

2. $q= q_0$q=q0​，最后可以删到只剩下一个状态。正则表达式为$R^*$R∗.

3. 当有$|F|\gt1$∣F∣>1，即有多个状态被接受时，将到达每个终态的正则表达式加起来。

技巧：删去的顺序不一定，可以先局部再整体。

例子：

• 另有状态消去法的形式化方法– CONVERT(G)，但其不适合手工操作，略去不表。

4.5 正则表达式→有限自动机

精髓：将正则表达式的匹配过程写成一个二叉树，然后中序遍历，按照几种基本结构将其画成自动机。
其实大多数时候是随手画。

基础：

归纳：

4.6 右线性文法→有限自动机

精髓：因为右线性文法每次会产生一个非终结符合一个终结符，将生成终结符作为自动机的转移条件，产生的非终结符作为下一个状态。
因为只产生终结符时应该是接受状态，但是文法中没有这个符号，所以就新建一个符号H，让终结符指向H，H被接受。
为了不引入空转移，根据是否能由S推出空串决定S的可接受性。

方法：设右线性文法$G＝（N，T，P，S）$G＝（N，T，P，S），构造一个与G等
价的有限自动机$NFA\ M＝（Q，T，δ，q_0，F）$NFA M＝（Q，T，δ，q0​，F），其中： $Q＝N \cup {H}$Q＝N∪H，$H$H为一个新增加的状态, $H\notin N$H∈/​N， $q_0＝S$q0​＝S.
$F=\begin{cases}\{H,S\},if\ S\rarr\epsilon \in P\\\{H\}\end{cases}$F={{H,S},if S→ϵ∈P{H}​
$\delta:$δ:
$B\in \delta(A,a)\ if\ A\rarr aB \in P\\H\in \delta(A,a)\ if\ A\rarr a \in P\\\delta(H,a)=\empty$B∈δ(A,a) if A→aB∈PH∈δ(A,a) if A→a∈Pδ(H,a)=∅
例子：

4.7 有限自动机→右线性文法

精髓：把$\delta$δ函数的转移看成是一个个生成式。

方法：设$NFA\ M＝（Q，T，δ，q_0，F）$NFA M＝（Q，T，δ，q0​，F），构造一个右线性文法$G＝（N，T，P，S）$G＝（N，T，P，S），其中$N＝Q$N＝Q， $S＝q_0$S＝q0​

$P:$P:
$A\rarr aB\ \in P\ if\ \delta(A,a)=B,\ then\ if\ B\in F,\ add\ A\to a\ to\ P$A→aB ∈P if δ(A,a)=B, then if B∈F, add A→a to P
例子：

4.8 DFA的最小化：填表算法

• 最小化：对DFA M的极小化是找出一个状态数比M少的
  DFA M1，使满足 L(M) = L(M1)。若DFA Ｍ不存在互为等价状态及不可达状态，则称 DFA Ｍ是最小化的.
• 状态偶对：两个状态的有序二元组称为状态偶对。
• 状态的等价和可区分：两者是对立的。对于某一DFA M，如果两个状态$q_0,q_1$q0​,q1​通过任意的串$\omega$ω都可以转移接收状态（不一定是同一个接收状态），则两者等价。反之两者可区分。
  即：设$DFA\ M = (Q，T，δ，q_0，F)$DFA M=(Q，T，δ，q0​，F)，若$q_x,q_y\in Q$qx​,qy​∈Q，对于$\forall \omega\in T^*$∀ω∈T∗，若$(q_x,\omega)┣^*(q_x,\epsilon)\leftrightarrow(q_y,\omega)┣^*(q_y,\epsilon)$(qx​,ω)┣∗(qx​,ϵ)↔(qy​,ω)┣∗(qy​,ϵ)，则$q_x,q_y$qx​,qy​等价，反之两者可区分。
• 不可达状态：即无法从$q_0$q0​输入任何字符串$\omega$ω到达的状态。

4.8.1 删除不可达状态

可以减小填表算法的负担。
从$q_0$q0​开始，迭代寻找(bfs)可以到达的状态$Q_{可达}$Q可达​，则$Q-Q_{可达}$Q−Q可达​即为不可达状态，删除不可达状态即含有其的转移条目。

4.8.2 填表算法

精髓：因为状态的等价关系是传递的，可以通过两两判断等价性来找出所有等价的状态。又因为是自反的、对称的，所以只需要一个$n\times n$n×n表格的下三角部分来记录，且不需要对角线。
如果没有理由认为两个状态是可区分的，那么就认为他们是等价的。

方法：

1. 基础：所有的终态和非终态是可区分的。
2. 归纳：如果某两个状态$q_x,q_y$qx​,qy​可以通过符号$a$a转移到两个可区分的状态，那么他们是可区分的。

例子：

4.8.3 等价状态的合并

将所有的状态根据等价性构成一个划分，将划分块用其等价类代替。
用等价类作为状态标记构造一个新的DFA，其转移关系为：如果原来不同划分之间至少有一种转移，那么这两个等价类增加一条转移。
即：设待最小化的DFA为$DFA\ A = (Q, T, \delta, q_0 , F )$DFA A=(Q,T,δ,q0​,F) ，最小化的自动机为$DFA\ B = (Q_B, T, \delta_B, [q0], F_B )$DFA B=(QB​,T,δB​,[q0],FB​) , 其中 $Q_B=\{ [q] | q\in Q\}$QB​={[q]∣q∈Q}, $\delta_B([q] ,a)=[\delta(q,a)]\}$δB​([q],a)=[δ(q,a)]}，$F_B = \{ [q] | q\in F\}$FB​={[q]∣q∈F}

4.8.4 例子

4.9 正则语言的泵引理

精髓：因为正则语言对应的是有限自动机，其状态数是有限的，那么由Pigeonhole Rule，对于无限的语言（有限语言可以通过“并”构成正则语言），如果其为正则语言，那么一定会在自动机的某一段绕圈来达到无限。

泵引理：正则语言中足够长的句子一定能拆成三段，并且中间一段重复0次或任意多次得到的句子仍然属于正则语言（可以Pumping in和Pumping out）。泵引理成立是正则语言的一个必要条件。

用泵引理来证明某语言不是正则语言

证明步骤

1. 选任意的n.
2. 找到一个满足以下条件的串$w\in L$w∈L (长度至少为n).
3. 任选满足$w = xyz ∧ y\ne \epsilon ∧ |xy| \le n$w=xyz∧y​=ϵ∧∣xy∣≤n 的$x,y,z$x,y,z
4. 找到一个 $k\ge0$k≥0, 使 $xy^kz \ne L$xykz​=L.

例子：利用泵引理证明下述语言不是正则语言：
$L=\{1^{n^2}|n\ge 0\}$L={1n2∣n≥0}
答：

1. 假设$L$L是正则语言。
2. 那么，存在$N\in Z^+$N∈Z+，对于$\forall \omega\in L(|\omega|\ge N)$∀ω∈L(∣ω∣≥N)满足泵引理。
3. 取$\omega = 1^{N^2}$ω=1N2，显然$\omega \in L$ω∈L且$|\omega|=N^2\ge N$∣ω∣=N2≥N。
4. 那么，$\omega$ω可以被分为$\omega =xyz$ω=xyz，且$|xy|\le N,|y| \gt 0$∣xy∣≤N,∣y∣>0.
5. 那么，$y$y只能是$1^m(m\gt 0)$1m(m>0),$x$x为$1^l(l\ge 0)$1l(l≥0)，$z$z为$1^{N^2-l-m}$1N2−l−m，且满足$m+l\le N$m+l≤N。
6. 那么$xy^2z=1^l1^{2m}1^{N^2-l-m}=1^{N^2+m}$xy2z=1l12m1N2−l−m=1N2+m。
7. 因为$m\gt 0$m>0所以$N^2+m\gt N^2$N2+m>N2；因为$m+l\le N$m+l≤N且$l\ge 0$l≥0，得$m\le N$m≤N，所以$N^2+m\le N^2+N\lt N^2+2N+1=(N+1)^2$N2+m≤N2+N<N2+2N+1=(N+1)2，所以$N^2\lt N^2+m\lt (N+1)^2$N2<N2+m<(N+1)2，即新串的长度严格位于两个完全平方数之间，所以其不是完全平方数。
8. 则$xy^2z\notin L$xy2z∈/​L，而由泵引理$xy^2z\in L$xy2z∈L，所以假设不成立，$L$L不是正则语言。

例子：由文法$G$G产生的语言$L(G)$L(G)，其中$P:S\to aSbS|c$P:S→aSbS∣c.
语言的描述有很多种，用类似$a^nb^n$anbn的公式化描述的只有一部分。还有用叙述性描述（比如a和b的数量一样多）和文法描述的（本题）。这些描述有时候很难写出完全等价的公式化描述，其实只需要其中的一个句子即可。

1. 假设L是正则语言，则存在正整数N，对于任意L内的字符串$\omega$ω成立$|\omega|\ge N$∣ω∣≥N时，可以应用泵引理。
2. 对于L，不妨取$\omega=a^Nc(bc)^N=\omega_1\omega_0\omega_2$ω=aNc(bc)N=ω1​ω0​ω2​，则$|\omega_0|\gt 0,|\omega_1\omega_0|\le N$∣ω0​∣>0,∣ω1​ω0​∣≤N，显然$\omega_0=a^i(i\gt 0)$ω0​=ai(i>0)。
3. 则对于$\omega'=\omega_1\omega_0^2\omega_2=a^{N+i}c(bc)^N$ω′=ω1​ω02​ω2​=aN+ic(bc)N，其不属于$L$L（注意是文法那个L，不是取的句子），而与泵引理矛盾，所以L不是正则语言。

4.10 双向有限自动机(2DFA)

双向有限自动机：读入一个字符之后，读头既可以左移一格， 也可以右移一格，或者不移动的有限自动机。

确定的双向有限自动机: 每读入一字符，必须向左或右移动，不考虑不移动的情况.

4.10.1 2DFA的五要素

$2DFA\ M＝(Q，T ，δ， q_0， F)$2DFA M＝(Q，T，δ，q0​，F)

$\delta:Q\times T\rarr Q\times\{L,R\}$δ:Q×T→Q×{L,R}
$\delta(q,a)=(p,R)\ or\ \delta(q,a)=(p,L)$δ(q,a)=(p,R) or δ(q,a)=(p,L)
其他与DFA相同。即每次除了状态转移之外还要移动读头（左移或右移一格）。

4.10.2 2DFA的格局

• 2DFA的格局和DFA的不同，要把字符串整个列出来。

• $δ(q，a_{m+1})=(p，R)$δ(q，am+1​)=(p，R)的格局表示：$a_1 a_2…a_m q a_{m+1}…a_n┣ a_1 a_2…a_{m+1} p a+{m+2}…a_n$a1​a2​…am​qam+1​…an​┣a1​a2​…am+1​pa+m+2…an​

• $δ(q，a_{m+1})=(p，L)$δ(q，am+1​)=(p，L)的格局表示: $a_1 a_2…a_m q a_{m+1}…a_n┣ a_1 a_2…a_{m-1} p a_m a_{m+1}…a_n$a1​a2​…am​qam+1​…an​┣a1​a2​…am−1​pam​am+1​…an​

4.10.3 2DFA接受的语言

• 2DFA接受的语言是$L(M)=\{ω| q_ω┣^*_ωq，q\in F\}$L(M)={ω∣qω​┣ω∗​q，q∈F}

4.11 有输出的有限自动机(Mealy&Moore)

有输出的有限自动机是有限自动机的一个类型.
这类自动机在有字符输入时，不仅存在状态转换， 同时引起字符输出.

根据输入字符，自动机状态，输出字符三者之 间关系，可有两类有输出的自动机:

米兰机(Mealy): 输出字符与输入字符及状态有关.
摩尔机(Moore): 输出字符仅与状态有关.

最大优点: 节省状态

4.11.1 Mealy机

• $M＝(Q，T ，R，δ， g ， q_0)$M＝(Q，T，R，δ，g，q0​)
  相比DFA，多了输出函数$g:Q\times T\rarr R$g:Q×T→R
  $\delta$δ和$g$g函数共同描述Mealy机的工作情况。

• 绘图：
  $\begin{cases}\delta(p,a)=q\\g(p,a)=b\end{cases}${δ(p,a)=qg(p,a)=b​
  绘制为

• 例子：
  
  

4.11.2 Moore机

• $M＝(Q，T ，R，δ， g ， q_0)$M＝(Q，T，R，δ，g，q0​)
  相比DFA，多了转移函数$g$g
  相比Mealy机，Moore机的转移函数$g$g是个一元函数，只与当前状态有关。

• 绘图：
  $\begin{cases}\delta(p,a)=q\\g(p)=b_1\\g(q)=b_2\end{cases}$⎩⎪⎨⎪⎧​δ(p,a)=qg(p)=b1​g(q)=b2​​
  绘制为

  因为输出只与状态有关，所以把输出写在状态圈里。

• 例子：

4.11.3 Moore机→Mealy机

• Moore机比较简单，所以转换成Mealy机很方便。
• 将Moore机中某个状态$q$q的输出$b$b，作为新的Mealy机任何到达$q$q状态的转移时的输出。
  即：设摩尔机$M＝(Q, T, R,δ, g ,q_0)$M＝(Q,T,R,δ,g,q0​) 米兰机$M’＝(Q, T, R,δ, g’, q_0)$M’＝(Q,T,R,δ,g’,q0​) 如果$中$中有$δ(q，a)=p$δ(q，a)=p，$ g§ = b$ 则$M’$M’中有$g’(q，a) = b = g(δ(q，a))$g’(q，a)=b=g(δ(q，a))

例子：

4.11.4 不做要求：Mealy机→Moore机

略去不表。