gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-03 01:23:13 25 4
gpt4 key购买 nike

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

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

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

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

最佳答案

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

关于regex - 设计 NFA 时如何直观思考,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20534449/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com