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)也是正则的
posted on 2023-09-09 08:11
春秋十二月 阅读(1098)
评论(0) 编辑 收藏 引用 所属分类:
Compute Theory