具有可变转换条件的 NFA/DFA
晚安,
假设我有一个实现 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 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(1)
请参阅以下实现,它采用 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