regex - 设计 NFA 时如何直观思考

Question

我不知道这个问题是否适合问，但我绝对觉得应该问。当然，我确实在互联网和 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的书，我自己也找到了答案)

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

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

非常欢迎任何“建设性”答案! 谢谢。

Answer 1

我倾向于从正则表达式开始，然后逆向工作。这通常可以帮助您形成解决问题的正确心态。从这里开始，建立正确的解决方案并比较两者就相对容易了。对于更复杂的问题，您可以使用 Thompson 的构造算法。另外，要找到 NFA 的补集，只需将接受状态替换为不接受状态即可。