1. 若DFA D是用子集构造法从NFA N构造出来的，则L(D)=L(N)

2. 一个语言L被某个DFA接受，当且仅当被某个NFA接受

3. 一个语言L被某个£-NFA接受，当且仅当被某个DFA接受

4. 若对于某个DFA A，L=L(A)，则存在一个正则表达式R使得L=L(R)

5. 每一个用正则表达式定义的语言也可用有穷自动机定义

6. 若通过填表算法不能区分两个状态，则它们是等价的

7. DFA的状态等价性是传递的

8. 若对于DFA每个状态q及与q等价的所有状态组成块，则不同的状态块形成状态集合的划分。也就是说，每个状态恰好属于一个块，同一块中的所有成员都是等价的，从不同块中选择的状态对都不是等价的

9. 根据等价状态划分算法最小化DFA D得到的DFA M是唯一的。也就是说，不存在其它等价于D的DFA N，其状态数比M少

10. 对于正则表达式，空集是并运算的单位元、连接运算的零元，空串是连接运算的单位元

11. 若L和M都是正则语言，则L和M的并、交、差也是

12. 若L是字母表T上的正则语言，则~L=T*—L也是

13. 若L是正则语言，则L的反转也是

14. 若L是字母表T上的正则语言，h是T上的一个同态，则h(L)也是正则的

15. 若h是字母表A到字母表T的同态，且L是T上的正则语言，则逆同态h^-1(L)也是正则的

春秋十二月 2023-09-09 08:11 发表评论