首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >州数最高- DFA / NFA

问州数最高- DFA / NFA
EN

Stack Overflow用户
提问于 2016-02-19 00:06:30
回答 1查看 1.8K关注 0票数 1

我试图把我的头脑集中在常规语言上的一些操作上,比如交叉、级联和Kleene星型(对于DFA和NFA,以及它们之间的区别)。

设想以下情况:

假设L_A和L_B是由DFAs、M_A和M_B定义的正则语言,、n_A、和n_B是M_A和M_B中的状态数。

两个问题脱颖而出:

  1. 在DFAs中,语言L_A*中所需的最高状态数是多少?
  2. 在NFAs中,L_A (交集) L_B所需的最高状态数是多少?

任何关于如何解决这些问题的help/pointers/advice都是被高度重视的!我不知道该从哪里开始。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2016-09-13 18:58:16

对于语言L_A*,在DFAs中您需要的状态数最多是多少?

“你需要的状态的最高数量”是另一种在Myhill-Nerode定理不可区分关系下要求等价类数量的方法。假设L_A“需要”x状态(在其最小DFA中),x小于或等于n_A,L_A*“需要”多少个状态?

当然,在某些情况下,L_A*“需要”的状态比L_A“少”。考虑语言{0,1} over{0,1};最小DFA有三种状态,而最小DFA用于{0,1}*有一种状态。

此外,不难想象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星来创建任何新的类。但我们肯定能摧毁他们!(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)*等效类中没有字符串,我们可以进一步压缩它。

但最重要的一点是,我们再也没有更多了;因此,关于“需要”状态数的理论最大值是x,其中x是L_A的“需要”状态数。

在NFA中,语言L_A (交集) L_B所需的最高状态数是多少?

设x <= n_A是L_A的“必需”数,y <= n_B是n_B的“必需”数。交集可以很容易地产生空语言,因此应该清楚,交集中的“所需”状态可能比x和y低得多。在这种情况下,如果L_A = L_B,因为L_A (交集) L_B = L_A (交集) L_A = L_A,则情况相同。

请注意,我们永远不需要超过x*y,因为我们总是可以使用笛卡儿积机器构造一个DFA,它的状态数等于L_A和L_B中状态数的乘积,而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态。这些DFAs中没有一个具有相应的对应NFAs,且状态较少。对于^2k的DFA具有转换表:

代码语言:javascript
复制
q    e    q'
q0   a    q1
q1   a    q2

随着q0的接受。因此,(可实现的)最大值是x_y <= n_A_n_B。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/35494961

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档