4

我不知道这个问题问得对不对，但我绝对觉得应该问。当然，我确实看到了很多关于互联网和 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.

哪里有艺术，我觉得哪里有直觉。如果这些问题涉及“设计”某些东西，那么每个人都必须有自己的方式（当然不会脱离定理或规则本身）来解决或解决这些问题。人们应该已经开发出一种思考过程（经过多年的实践）来解决这些问题。

 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 的书，我自己也找到了解决方案）

我只想知道，如何培养解决问题的直觉。

我问这个问题是为了培养所有在解决这些问题时遇到困难的初学者（像我一样）的技能和思维过程，即使他们（包括我）对这些主题有足够的理论知识。

任何“建设性”的答案都非常受欢迎！！谢谢你。

4

1 回答 1

1

I tend to start out with a regular expression and work backwards. That usually helps you get into the correct mindset for the problem. From there it is relatively easy to build up the correct solution and compare the two. For more complicated problems you can use Thompson's Construction algorithm. Also to find the complement of an NFA simply swap the accepting states for the non accepting states.

于 2013-12-31T09:55:27.157 回答