最多的状态 - DFA / NFA
Highest number of states - DFA / NFA
我正在尝试围绕常规语言的一些操作进行思考，例如 intersection、concatenation 和 Kleene star（对于 DFA 和 NFA，以及它们的不同之处）。
想象一下：
Assume we have L_A and L_B as regular languages defined by DFAs M_A and M_B
And n_A and n_B are the number of states in M_A and M_B.
两个问题脱颖而出：
语言 在 DFA 中您需要的最大状态数是多少L_A*?
语言 在 NFAs 中你需要的最大状态数是多少L_A（路口）L_B?
关于如何解决这些问题的任何 help/pointers/advice 都非常有价值！我不知道如何或从哪里开始。
What is the highest number of states you would need in DFAs for the language L_A*?
"highest number of states you would need" 是在 Myhill-Nerode 定理的不可区分关系下求等价数 class 的另一种方法。假设 L_A "needs" x 个状态（在其最小 DFA 中），其中 x 小于或等于 n_A。有多少个州可能 L_A* "need"?
当然有 L_A* "needs" 个状态比 L_A 个少的情况。考虑 {0, 1} 之上的语言 {0, 1}；这个的最小 DFA 具有三个状态，而 {0, 1}* 的最小 DFA 具有一个状态。
此外，不难想象 L_A* "needs" 状态数量相同的语言：例如，当 L = L* 时。假设 L_A = {0, 1}。那么L_A = {0, 1}** = {0, 1}* = L和L_A* "needs"状态数相同。
我认为你的问题实际上是关于我们需要更多的情况，特别是在最坏的情况下我们可能还需要多少。假设 L_A 的等价 class 是 c_1, c_2, ..., c_x。将这些视为将 class 中的字符串转换为 L_A 中的字符串的字符串集。那么L_A*的class就是(c_1)(L_A*) + e, (c_2)(L_A*), ...，（c_w）（L_A*）。因此，不同 classes 的最大数量是 w；我们不能通过应用 Kleene 星来创建任何新的 classes。但我们当然可以摧毁它们！有可能 (c_a)(L_A)* = (c_b)(L_A)* 对于 a != b。考虑 L_A = {0, 1}。那么 c_1 = {0, 1}, c_2 = {e}, c_3 = {}。然后 (c_1)(L_A)* + e = {e, 0, 1, ...}, (c_2)(L_A)* = {e, 0、1、...}、(c_3)(L_A)* = {}。我们最终使用这种方法得到了两个不同的候选者，我们可以通过注意到 (c_3)(L_A)* 等价 class.[ 中没有字符串来进一步削减它。 =13=]
但重要的是我们永远不能拥有更多；因此 "needed" 状态数的理论最大值是 x，其中 x 是 "needed" 状态数 L_A.
What is the highest number of states you would need in NFAs for the language L_A (intersection) L_B?
令 x <= n_A 为 L_A 的数字 "needed" 并且 y <= n_B 为 [=86= 的数字 "needed" ].交叉很容易导致，例如，空语言，所以应该清楚交叉中的 "needed" 状态可能比 x 和 y 低得多。如果 L_A = L_B 是一样的 因为 L_A （交集） L_B = L_A （交集） L_A = L_A 那样的话。
请注意，我们永远不需要超过 x*y，因为我们总是可以使用笛卡尔乘积机构造来构造一个 DFA，其状态数等于 [=46] 的 DFA 中状态数的乘积=] 和 L_B，并且 DFA 是 NFA。一个自然的问题是，对于 L_A 和 L_B 中的某些 class 语言，是否达到了这个限制。答案是肯定的。
考虑 L_A = {a^nk} 和 L_B = {a^mk} 其中 n 和 m 互质且大于一。然后L_A（交点）L_B = {a^(nm)}。 L_A 的最小 DFA 有 n 个状态，L_B 的最小 DFA 有 m 个状态。 L_A（交叉点）L_B 的最小 DFA 具有 nm 个状态。 None 这些 DFA 具有相应的等效 NFA，但状态更少。 a^2k 的 DFA 具有转换 table:
q e q'
q0 a q1
q1 a q2
接受 q0。因此（可实现的）最大值为 xy <= n_An_B.
我正在尝试围绕常规语言的一些操作进行思考，例如 intersection、concatenation 和 Kleene star（对于 DFA 和 NFA，以及它们的不同之处）。
想象一下：
Assume we have L_A and L_B as regular languages defined by DFAs M_A and M_B And n_A and n_B are the number of states in M_A and M_B.
两个问题脱颖而出：
语言 在 DFA 中您需要的最大状态数是多少L_A*?
语言 在 NFAs 中你需要的最大状态数是多少L_A（路口）L_B?
关于如何解决这些问题的任何 help/pointers/advice 都非常有价值！我不知道如何或从哪里开始。
What is the highest number of states you would need in DFAs for the language L_A*?
"highest number of states you would need" 是在 Myhill-Nerode 定理的不可区分关系下求等价数 class 的另一种方法。假设 L_A "needs" x 个状态（在其最小 DFA 中），其中 x 小于或等于 n_A。有多少个州可能 L_A* "need"?
当然有 L_A* "needs" 个状态比 L_A 个少的情况。考虑 {0, 1} 之上的语言 {0, 1}；这个的最小 DFA 具有三个状态，而 {0, 1}* 的最小 DFA 具有一个状态。
此外，不难想象 L_A* "needs" 状态数量相同的语言：例如，当 L = L* 时。假设 L_A = {0, 1}。那么L_A = {0, 1}** = {0, 1}* = L和L_A* "needs"状态数相同。
我认为你的问题实际上是关于我们需要更多的情况，特别是在最坏的情况下我们可能还需要多少。假设 L_A 的等价 class 是 c_1, c_2, ..., c_x。将这些视为将 class 中的字符串转换为 L_A 中的字符串的字符串集。那么L_A*的class就是(c_1)(L_A*) + e, (c_2)(L_A*), ...，（c_w）（L_A*）。因此，不同 classes 的最大数量是 w；我们不能通过应用 Kleene 星来创建任何新的 classes。但我们当然可以摧毁它们！有可能 (c_a)(L_A)* = (c_b)(L_A)* 对于 a != b。考虑 L_A = {0, 1}。那么 c_1 = {0, 1}, c_2 = {e}, c_3 = {}。然后 (c_1)(L_A)* + e = {e, 0, 1, ...}, (c_2)(L_A)* = {e, 0、1、...}、(c_3)(L_A)* = {}。我们最终使用这种方法得到了两个不同的候选者，我们可以通过注意到 (c_3)(L_A)* 等价 class.[ 中没有字符串来进一步削减它。 =13=]
但重要的是我们永远不能拥有更多；因此 "needed" 状态数的理论最大值是 x，其中 x 是 "needed" 状态数 L_A.
What is the highest number of states you would need in NFAs for the language L_A (intersection) L_B?
令 x <= n_A 为 L_A 的数字 "needed" 并且 y <= n_B 为 [=86= 的数字 "needed" ].交叉很容易导致，例如，空语言，所以应该清楚交叉中的 "needed" 状态可能比 x 和 y 低得多。如果 L_A = L_B 是一样的 因为 L_A （交集） L_B = L_A （交集） L_A = L_A 那样的话。
请注意，我们永远不需要超过 x*y，因为我们总是可以使用笛卡尔乘积机构造来构造一个 DFA，其状态数等于 [=46] 的 DFA 中状态数的乘积=] 和 L_B，并且 DFA 是 NFA。一个自然的问题是，对于 L_A 和 L_B 中的某些 class 语言，是否达到了这个限制。答案是肯定的。
考虑 L_A = {a^nk} 和 L_B = {a^mk} 其中 n 和 m 互质且大于一。然后L_A（交点）L_B = {a^(nm)}。 L_A 的最小 DFA 有 n 个状态，L_B 的最小 DFA 有 m 个状态。 L_A（交叉点）L_B 的最小 DFA 具有 nm 个状态。 None 这些 DFA 具有相应的等效 NFA，但状态更少。 a^2k 的 DFA 具有转换 table:
q e q'
q0 a q1
q1 a q2
接受 q0。因此（可实现的）最大值为 xy <= n_An_B.