我试图总结我的周围正规语言的一些操作头，如路口，串联和克林星（适用于DFA和NFA，以及它们是如何不同）。最高的国家的数量 - DFA/NFA
想象一下以下内容：
假设我们有L_A和L_B为正规语言通过的DFA M_A和M_B 而N_A和N_B定义是M_A的许多州和M_B。
两个问题脱颖而出：
什么是国家的最高数你就需要在的DFA的语言L_A *？
是什么状态你需要在的NFA的语言L_A（路口）L_B的次数最多？
任何帮助/指针/咨询如何去解决这些问题的高度重视！我不知道如何或从哪里开始。
在语言L_A *中，您需要在DFA中使用的最多状态数是多少？
“你需要的最多状态数”是另一种在Myhill-Nerode定理的不可区分性关系下询问等价类的数量的方法。假设L_A“需要”x个状态（在其最小DFA中），其中x小于或等于n_A。 L_A *“需要”多少个州？
当然有些情况下L_A *“需要”比L_A更少的状态。考虑{0,1}上的语言{0,1};针对此的最小DFA具有三个状态，而针对{0,1} *的最小DFA具有一个状态。此外，不难想象L_A *“需要”相同数量的状态的语言：例如，当L = L *时。假设L_A = {0,1} 。那么L_A = {0,1} ** = {0,1} * = L并且L_A *“需要”相同数量的状态。
我认为你的问题实际上是关于我们需要更多的情况，特别是在最坏的情况下我们可能需要更多的情况。假设L_A的等价类是c_1，c_2，...，c_x。考虑这些是将类中的字符串转换为L_A中的字符串的字符串集合。那么L_A *的类是（c_1）（L_A *）+ e，（c_2）（L_A *），...，（c_w）（L_A *）。因此，不同类别的最大数量是w;我们不能通过应用Kleene星来创建任何新类。但是我们当然可以摧毁它们！对于a = b，有可能是（c_a）（L_A）* =（c_b）（L_A）*。考虑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）*等价类中没有字符串来进一步减少它。
但重要的一点是，我们永远不会有更多;所以“需要”状态数量的理论最大值是x，其中x是L_A的“需要”状态数量。
在语言L_A（交叉点）L_B中，您需要在NFA中使用的状态数量是多少？
设x = <是N_A “需要” 的个数为L_A和y < = N_B是 “需要” 对N_B数。交叉点很容易导致例如空语言，所以应该清楚交叉点中的“需要”状态可能远低于x和y。在这种情况下，由于L_A（交点）L_B = L_A（交点）L_A = L_A，因此如果L_A = L_B则相同。
请注意，我们永远不需要超过x * y，因为我们始终可以使用笛卡尔乘积机构造来构造一个DFA，其状态数等于L_A和L_B的DFA状态数的乘积，而DFA是NFA。一个自然的问题是这个限制是否达到了某种语言L_A和L_B的限制。答案就是这样。考虑L_A = {a^nk}和L_B = {a^mk}其中n和m是相对的质数且大于1。然后L_A（交点）L_B = {a ^（nm）}。 L_A的最小DFA具有n个状态，而L_B的最小DFA具有m个状态。 L_A（交集）L_B的最小DFA具有nm个状态。这些DFA都没有相应的具有较少状态的等效NFA。^2k的DFA具有转换表：
q e q'
q0 a q1
q1 a q2
q0接受。因此，（可实现的）最大值是x y < = n_A n_B。