加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 百科 > 正文

正则表达式 – 如何在设计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的补充,只需将接受状态替换为非接受状态.

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读