数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究说明DFA和NFA中语言的最坏情况状态数。
确定性有限自动机（DFA）是一个五元组
M=(Q, ∑, δ,q0,F)
其中，
Q - 有限状态集。
∑ - 有限字母表集。
δ - Q × ∑ → Q 是转移函数。
q0 ∈ Q 是起始状态或初始状态。
F - 结束状态或接受状态。
让我们看看语言A∩B 和 A*的DFA中状态的最坏情况数量。
假设A和B是两个状态，
|A| = 状态数 = nA
|B| = 状态数 = nB
DFA = |A∩B|
=nA.nB
|A ∪ B| =nA.nB
|A*|=3/4 2nA
|AB| = nA (2nB-2nB-1)
NFA
非确定性有限自动机（NFA）也与DFA具有五个相同的状态，但转移函数不同，如下所示：
δ: Q X ∑ -> 2Q
其中，
Q - 有限状态集。
∑ - 输入符号的有限集。
q0 - 初始状态。
F - 结束状态。
δ - 转移函数。
让我们看看语言A∩B 和 A*的NFA中状态的最坏情况数量。
假设A和B是两个状态，
|A| = 状态数 = nA
|B|= 状态数 = nB
NFA
|AUB| = nA+nB+1
|A*| = nA+1
|AB| = nA+nB
|A∩B| = nA.nB
更新于：2021年6月16日
430 次查看
广告