具有可变转换条件的 NFA/DFA

发布于 2024-09-28 11:14:41 字数 190 浏览 3 评论 0原文

晚安,

假设我有一个实现 NFA/DFA 的类,其转换存储在 .NET 字典结构中,并且它接受输入单词并识别可通过某种方式从输入派生的一组单词。此外,我们假设自动机是一个通用模板,只需重新标记过渡字符即可应用于相同长度的不同单词。在字典中对转换函数进行编码以便可以在运行时根据输入单词的字符重新标记其转换的最佳方法是什么?

非常感谢。

Good night,

Let's suppose I have a class which implements a NFA/DFA whose transitions are stored in a .NET Dictionary structure, and which takes an input word and recognizes a set of words derivable in some way from the input. Furthermore, let's suppose that the automaton is a generic template that can be applied to different words of the same length with only a re-labeling of the transition characters. What is the best way to encode the transition function in the Dictionary so that it's transitions can be re-labeled according to the input word's characters at runtime?

Thank you very much.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

冬天旳寂寞 2024-10-05 11:14:41

请参阅以下实现,它采用 NFA 并使用字典将其转换为 DFA(然后转换为图形),就像您自己一样:

NFA 到 DFA

我不确定它是否具有您正在寻求的动态重新标记功能,但它有很好的(内联)记录,因此您可能会得到很多帮助您完成项目的想法。

还有一篇关于 lambda 转换主题的好(更新的)文章,但该文章的图像链接不再有效。不过,它确实附带了可下载的源代码FSAutomata.zip,您可以在阅读后检查文章:

NFA 与 Lambda 转换

Please see the following implementation which takes an NFA and converts it to a DFA (and then to a graph) using a dictionary, just like yourself:

NFA to DFA

I am uncertain whether it has the dynamic relabeling capability you are seeking, but it is very well (in-line) documented, so you may get many ideas to help you with your project.

There is also a good (more recent) article on the topic of lambda transitions, but the image links of the article are no longer valid. However it does come with downloadable source code FSAutomata.zip that you can examine after reading the article:

NFA with Lambda Transition

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文