正则表达式 – 如何在设计NFA时直观地思考
发布时间:2020-12-14 05:47:11 所属栏目:百科 来源:网络整理
导读:我不知道这个问题是否正确,但我绝对觉得应该问这个问题.当然,我确实看到了很多很好的和提供信息的问题,关于inter-net和StackOverflow本身的文章.但我发现所有问题或文章都遵循特定的规则或模式来解释主题.我的意思是,当问到关于NFA,DFA或正则表达式的问题时,
我不知道这个问题是否正确,但我绝对觉得应该问这个问题.当然,我确实看到了很多很好的和提供信息的问题,关于inter-net和StackOverflow本身的文章.但我发现所有问题或文章都遵循特定的规则或模式来解释主题.我的意思是,当问到关于NFA,DFA或正则表达式的问题时,提出了一个解决方案,这个问题遵循这些主题的定理/规则(计算理论).
But what I feel is that,as most of the questions on DFA/NFA are of the type "Design an NFA...." or "design a DFA...",i feel that developing/Designing DFA/NFA must be an ART. 有ART的地方我觉得有直觉.如果这些问题涉及“设计”某些事情,那么每个人都必须有自己的方式(当然不会偏离定理或规则)来解决或攻击这些问题. So I would like all the experts over this Site to share their knowledge (preferably in simple words) how they think over the problems (simple ones) of these topics. 我想用一个简单的例子来详细说明这个问题. 考虑问题: Let F be the language of all strings over {0,1} that do not contain a pair of 1s that are separated by an odd number of symbols. Give the state diagram of a DFA with five states that recognizes F . 要么 Design an NFA to find a 4-state NFA for the complement of F . (这些问题来自Sipser的书,我自己也找到了解决方案) 我只想知道,如何培养解决问题的直觉. 我问这个问题,考虑发展所有的技能和思维过程 任何“建设性的”答案都非常受欢迎! 解决方法
我倾向于从正则表达开始并向后工作.这通常可以帮助您深入了解问题的正确心态.从那里建立正确的解决方案并比较两者是相对容易的.对于更复杂的问题,您可以使用Thompson的构造算法.另外,为了找到NFA的补充,只需将接受状态替换为非接受状态.
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |