我不知道这个问题是否正确,但我绝对觉得应该问这个问题.当然,我确实看到了很多很好的和提供信息的问题,关于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的补充,只需将接受状态替换为非接受状态.
