形式语言与自动机_3(part)

3.9 右线性语言的性质

1. 等价和可区分的概念
   设DFA M = (Q，T，δ，q0，F)
   对不同的状态q１， q２∈Q 和每个ω∈T*，
   如果有

   

2. 不可达状态
   如果不存在任何$\omega \in T^*$，使$(q_０,\omega)┣* (q,\varepsilon)$，
   则称状态q∈Q为不可达状态。

3. 最小化
   若DFA Ｍ不存在互为等价状态及不可达状态，则称DFA Ｍ是最小化的。

最小化算法

一个DFA Ｍ的最小化，是把Ｍ的状态集Ｑ构成一个划分。即: 任何两个子集的状态都是可区分的；同一子集中的任何两个状态都是等价的。之后，每个子集用一个状态代表，并取一个状态名。
构成划分的步骤:
构成基本划分 $\Pi$={$\Pi^{‘}$, $\Pi^{‘’}$}， ($\Pi^{‘}$为终态集， $\Pi^{‘’}$为非终态集)
细分 $\Pi$ ={$\Pi^1$，$\Pi^2$,….., $\Pi^n$}，　　 $\forall \Pi^i$ ∈ $\Pi$
　　　 $\Pi^i ={ q_１， q_２，…， q_ｍ}$
当输入任意字符a时，若$\Pi^i$中的状态经标a的边可到达的状态集的元素分属于两个不同的子集中，则将$\Pi^i$细分为两个子集.
重复步骤(2)，直至不可再细分，得到Ｍ1.
若Ｍ1中有不可达状态，将其删除，Ｍ1便是最小化的.

优化步骤：

一个例子：

填表法的例子：

针对正则语言的 Pumping 引理

中文是 泵浦

泵浦引理的性质和地位：

• 正则语言应满足的一个必要条件
• 用于判定给定的语言不是正则集。

物理意义：当给定一个正则集和该集合上一个足够长的字符串时，在该字符串中能找到一个非空的子串，并使子串重复，从而组成新的字符串。该新串必在同一个正则集内。

定理：
设L是正则集，存在常数k，对字符串$ω\in Ｌ$ 且$｜ω｜≥ｋ$，
则ω可写成$ω_1ω_0ω_２$，其中$｜ω_1ω_0｜≤ｋ$，$｜ω_0｜＞０$，
对所有的ｉ≥0有$ω_1ω_0^iω_２$∈Ｌ。

证明：
运用了鸽巢原理
pumping特性：
任一长度不小于状态数目的字符串所标记的路径上，必然出现重复的状态.

泵浦引理的应用

注意：ω的取法有技巧， 一定要能推出矛盾才可以。
如：

右线性语言的封闭性 (已经忘光光了草哦)

自动机到了终态但是串没读完不算到了终态
当从带空的NFA到不带空的NFA转换时，如果状态q0不能接受b，还不能下定论，应该看q0的空闭包能不能接受b